참고
에라토스테네스의 체
NOTE
소수를 판별하는 알고리즘!
에라토네스 알고리즘 흐름
•
어떤 수의 소수의 여부를 확인 할 때는, 특정 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)로 구할 수 있다.
•
만약 대량의 소수를 한꺼번에 판별할 경우 에라토네스의 체를 사용한다.
구현 코드
NOTE
function 에라토스테네스의_체(int N):
소수배열 = boolean[N+1] 배열 생성, 모든 값은 true로 초기화
소수배열[0] = false
소수배열[1] = false
소수목록 = 빈 리스트 생성
for i = 2 to sqrt(N):
if 소수배열[i] == true:
for j = i^2 to N by steps of i:
소수배열[j] = false
for i = 2 to N:
if 소수배열[i] == true:
소수목록에 i 추가
return 소수목록
Java
복사