소수찾기-에라토스테네스의 체

소수와 에라토스테네스의 체

소수

: 자기 자신과 1만을 약수로 가지는 수. (ex, 2, 3, 5, 7…,(1제외))

소수 구하는 방법

: 해당 숫자를 1, 2, 3, 4, 5… 순서대로 나누어보며 확인 => 연산이 많아짐.

에라토스테네스의 체

: 어떤 수의 배수는 소수가 아니라는 특성을 활용.

2의 배수 제외, 3의 배수 제외, (4는 2의 배수라 이미 제외됨), 5의 배수 제외…..

Q. n보다 작은 소수의 개수?

1) 1~n까지 중에서 2의 배수, 3의 배수,,, 이렇게 지워나가면 됨. 2) 언제까지? n의 Square Root까지: n=루트n X 루트n일 때, 루트n이 스퀘어 루트. 그 이후로는 이미 체에서 걸러짐.

int[] arr = new int [n]; // 인덱스 = 숫자, 해당 숫자가 소수면 1, 소수가 아니면 0 => 마지막에 1을 다 더해주면 소수개수 확인

for(int i = 2; i < n; i++) { // 1로 전체 초기화
	arr[i] = 1; 
}

for(int i = 2; i<= (int)Math.sqrt(n); i++) { // Square Root까지만 for문 돌림
	if(arr[i] == 0) { // 이미 배수면 아무것도 안함
		continue;
	}
	
	int num = i*2; // 맨 처음수 제외
	while (num<n) { // 그 다음 수부터 n까지
		arr[num] = 0; // 소수가 아니라고 표시함
		num += i; // i 만큼 늘려가며(X2, X3,,,)
	}
}

---

마지막 수정일시: 2022-05-30 13:07