소수 개수 세는 법 공식이나 발상 아시는분 알려주세요.

Question

2 3 5 7 …예를 들어 100보다 작은 정수 중에 소수 세는 법 같은거..공식이나 발상 아시는분 댓글 부탁드립니다.

포카칩 · Accepted Answer

한번 연구해보세요 ㅋㅋㅋ

미스터옥토버 · Answer

우문현답 감사합니다.

해볼께요~

Декабристы · Answer

없어요

sos440 · Answer

소수를 찾는 것은 아직도 수학자들에게 있어 가장 어려운 난제 중 하나입니다.

현재까지 알려전 어떤 기발한 방법 - 특정 수 N 이하의 모든 소수의 목록을 작성하는 알고리즘 - 도 결국 에라스토테네스의 체와 비교하면 비약적으로 효율적이지 않습니다.

에라스토테네스의 체의 복잡도는 대략 O(N)인데, 2004년에 Atkin이 발견한 Atkin의 체는 O(N/loglogN) 정도로, 여기서 등장하는 1/loglogN 이라는 값운 N이 1억이어도 고작 0.3432 정도밖에 되지 않습니다.

열등한 이과종자 · Answer

발딲고자는게 더 이롭습니다

소수 개수 세는 법 공식이나 발상 아시는분 알려주세요.

최근 게시글 · 더보기

댓글이 많은 글