코딩 07. 소수 구하기

소수란 ? 1과 자신으로만 나누어지는 수

int n = 100;
boolean boo;

for(int i = 2; i < n; i++) {	// 1은 소수가 아니기 때문에 제외
	boo = true;
	for(int j = 2; j <= i/2; j++) {
		if(i%j == 0) {
			boo = false;
			break;
		}
	}
	if (boo == true) System.out.printf("%3d", i);
}

자연수 i를 2로 나눈 이유는,
예를 들어 자연수 8을 소인수분해하면 1, 2, 4, 8이 나오는데 1과 8이 짝꿍이고, 2와 4가 짝꿍이기 때문에 1, 2 이후에 나오는 4, 8은 신경쓸 필요가 없어진다.

:-D ? 에라토스테네스의 체

int n = 15;
int arr[] = new int[n];

for (int i = 0; i < n; i++) {
	arr[i] = i + 1;
}

for (int i = 2; i <= n; i++) {
	if (arr[i - 1] == 0)
		continue;
	int j = 2;
		
	while ((i * j) - 1 < n) {
		arr[(i * j) - 1] = 0;
		j++;
	}
}

2부터 시작해서 2의 배수를 지운다.
다음은 3의 배수를 지운다.
4의 배수는 2의 배수이기 때문에 지워져있다.
5의 배수를 지운다.
6은 2, 3의 배수이기 때문에 지워져있다.
.
.
.
이런식으로 가면 2, 3, 5, 7, 11 ... 이 나온다.

이미지 출처 '성림원북스'