[알고리즘] 소수 판별 알고리즘

 

1. O(√n)

2부터 √n까지 나눠서 나머지가 0이 아니면 소수다.

∵ 만약 √n 이후에 나눠서 나머지가 0이 되는 수가 있다면, 그 수와 1~√n 사이의 수랑 곱해져서 n이 되는데, 그전에 필터링이 되지 않았다는 뜻이므로 이는 모순이다.

 

bool isPrimeNum(int n) {
	if (n == 1) return false;
	else if (n == 2) return true;
	else if (n%2 == 0) return false;
	else {
		for (int i=3; i*i <= n; i+=2) {
			if (n%i == 0) return false;
		}
		return true;
	}
}

이 코드에서 실수할 수 있는 부분은 L3과 L4의 순서가 바뀌면 안 된다는 점

 

 

 

2. 에라토스테네스의 체

void Eratos(int n) {
	for (int i=2; i<=n; i++) {
		isPrime[i] = true;
	}
	for (int i=2; i*i <= n; i++) {
		for(int j=i+i; j<=n; j+=i) {
			isPrime[j] = false;
		}
	}
}