밍의 기록들😉

[수학] 1부터 N까지 소수 구하기(에라토스테네스의 체) 본문

자료구조, 알고리즘/기본다지기

[수학] 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는 범위를 넘어가기 때문이다. 


0 Comments
댓글쓰기 폼