현재 존재하는 알고리즘중에 2084575292398472941972398592175983752983759265201840174896574867235204801574578457194058027512347197485701471093741057057289457928374927492470275029750151651865194699856916863458746381765198736584356318765487563874561387543687561837618765438756384756384756348756384756487568735643875648375648756478587653487563785673485647854378567834564736537485675675674865786786574856487654837654837564873657843658346584365891이라는 수가 소수인지 아닌지 단순계산이 아닌 알고리즘으로 풀 수 있는게 있음? 그리고 만약 소수공식이 발견돼도 그안에 이런 큰 수를 대입했을 때 걸릴 시간은 결국 알고리즘과 크게 달라지지 않으면 그게 의미가 있는걸까? 공식과 알고리즘의 명확한 차이가 뭘까 그리고 수학자들이 소수찾는 알고리즘 말고 공식에 몰두하는 이유가
[일반] 소수에 규칙이 있긴 함? 하물며 알고리즘이라도
익명(220.84)
2020-07-21 19:02
추천 0
댓글 25
다른 게시글
-
수학사 책 빌렸음 [2][일반] 익명(1.251) | 20.07.21추천 0
-
학부 대수학 질문입니다 x2 !! [7][일반] 집피(apororo) | 20.07.21추천 0
-
학부 대수학 질문입니다 x1 !! [6][일반] 집피(apororo) | 20.07.21추천 0
-
항수항 급수의 미분문제 막혔는데 좀 도와줘요 ㅠ [13][일반] 핑크베리(117.111) | 20.07.21추천 0
-
해석학 질문합니다 [8][일반] 해석학(223.38) | 20.07.21추천 2
-
니들이 부럽다 나는 빡대가리라 중학수학도 다 이해못하는데 [3][일반] 익명(223.62) | 20.07.21추천 0
-
죽기 전에 페렐만이 기막힌거 하나 들고 왔으면 [1][일반] 익명(49.167) | 20.07.21추천 0
-
5년내로 리만가설 증명되고 100만원잃기 vs [9][일반] 익명(118.235) | 20.07.21추천 0
-
임고문제가 잼없는 이유가 [2][일반] 익명(223.38) | 20.07.20추천 0
-
시발.. 이 모든게 다 시뮬레이션이었으면 [2][일반] ㅁ(218.239) | 20.07.20추천 0
윌런스의 공식
무엇보다 그게 단순계산 아니면 뭐임
그럼 단순계산의 정의가 뭔데
소수들을 하나하나 짚어가며 계산하는거
저거보다 작은 소수로 다 나눠보면 되는데 왜 없음? - dc App
글을 제대로 읽어 분명 단순계산이 아닌 알고리즘 얘기하는거다
알고리즘이 뭔진 아노 게이야...? - dc App
그런 병신 알고리즘 말고 게.이.야 일일히 나누어보는게 에라토스테네스의 체와 효율이 뭐가 다른지 글이 이해가 안가노?
왜 그렇냐하면 알고리즘으로 하면 추세가 눈에 안 보이기때문에 직접 계산에 적용하면 또다시 추세가 나올 뿐임. 반면에 공식이 있으면 그냥 때려넣으면 새로운 공식이 나옴
AKS, 밀러-라빈, 스트라센같은 거 말하는 거임?
Primality test는 Poly-time algorithm이 있는데용
시간복잡도가 가장 작은 알고리즘이 뭔지 혹시 알고 있나용
생각해보니까 애초에 n^(1/2) time인데
작성자가 말하고 싶은건 소인수분해인가봄
젤 짧은거는 모르겠네용
O(n^(1/2)) algorithm은 exponential time algorithm이죵. 숫자 n을 입력할때 1을 n개적는식으로 입력하는 사람은 없으니까
윌슨의 정리
https://www.google.com/search?q=소수판별법&oq=소수판별법&aqs=chrome..69i57.5662j0j7&client=ms-android-samsung-ss&sourceid=chrome-mobile&ie=UTF-8
소수인지 아닌지 판별하는건 소수 규칙이랑 별개로 존나 쉬운건데
소수 규칙도 결국엔 소수인지 아닌지 판별할 수 있는건데. 존나 쉬운게 있고 존나 어려운게 있을 뿐
확률적 알고리즘은 옛날 옛적부터 있었구용 밀러-라빈 소수판별같은거 랜덤없는 알고리즘으로는 AKS 소수판별법이 있음.
여기 개념글에도 하나 있었음
https://gall.dcinside.com/mgallery/board/view/?id=math&no=15603&_rk=CFQ&exception_mode=recommend&page=1
보통 라이브러리에서는 목적에 따라 밀러-라빈이나 베일리-PSW같은거 쓸거여요
N이 소수인지 알고 싶으면 n번째 열의 파스칼의 삼각형을 계산한 뒤 맨 앞 뒤 1을 제외한 모든 숫자가 n으로 나뉘어지는지 확인하면 됨. P대 NP 문제로 말할 거 같으면 P로 풀 수 있는 거임.
"알고리즘"이라고 너는 말했는데 너가 모호하게 말했지만 말하는 거 봐선 P냐 NP냐를 물어본 거 같음