소수 개수 세는 법 공식이나 발상 아시는분 알려주세요.
2 3 5 7 …
예를 들어 100보다 작은 정수 중에 소수 세는 법 같은거..
공식이나 발상 아시는분 댓글 부탁드립니다.
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
-
1일차 1
-
-
-
-
-
-
-
-
-
-
-
-
-
https://orbi.kr/22a3e0b6-cc4d-4d73-9ba3-8312342...
-
-
-
다시시작
한번 연구해보세요 ㅋㅋㅋ
우문현답 감사합니다.
해볼께요~
없어요
소수를 찾는 것은 아직도 수학자들에게 있어 가장 어려운 난제 중 하나입니다.
현재까지 알려전 어떤 기발한 방법 - 특정 수 N 이하의 모든 소수의 목록을 작성하는 알고리즘 - 도 결국 에라스토테네스의 체와 비교하면 비약적으로 효율적이지 않습니다.
에라스토테네스의 체의 복잡도는 대략 O(N)인데, 2004년에 Atkin이 발견한 Atkin의 체는 O(N/loglogN) 정도로, 여기서 등장하는 1/loglogN 이라는 값운 N이 1억이어도 고작 0.3432 정도밖에 되지 않습니다.
발딲고자는게 더 이롭습니다
발견하신다면 필즈상..
골드바흐의 추측 생각나네요 ㅋ
대한민국 최초 필즈메달이 나오길 기대해봅니다 ㅋㅋ