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

에라토스테네스의 체

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