자료구조, 알고리즘/기본다지기
[수학] 1부터 N까지 소수 구하기(에라토스테네스의 체)
민쓰
2018. 8. 17. 00:27
에라토스테네스의 체
1부터 N까지 범위 안에 들어가는 모든 소수를 구하기 위해 에라토스테네스의 체를 사용한다.
1) 2부터 N까지 모든 수를 쓴다.
2) 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
3) 그 수는 소수이다.
4) 그 수의 배수를 모두 지운다.
코드
int n = 100; // 100까지 소수 int[]p = new int[100]; // 소수 저장 int pn = 0; // 소수의 개수 boolean c[] = new boolean[101]; //지워졌으면 true for(int i=2; i<=n; i++){ p[pn++] = i; for(int j=i*i; j<=n; j=j+i){ c[j] = true; } }
- c[j] == true 지워짐
- c[j] == false 지워지지 않음
- 안쪽 for문 (j)는 N의 크기에 따라서 i*i 또는 i*2로 바꾸는 것이 좋다.
- i가 백만인 경우 i*i는 범위를 넘어가기 때문이다.