소수(prime number)는 어떤 정수 a를 정수 b로 나눌때 나머지가 0인 b가 정확하게 다른 두 정수 값이 존재하면 그것을 소수라고 한다. 정의에 의해 1은 prime이 아니다. 1은 오직 1 하나에 의해서 나누어 지기 때문에 소수가 될 수 없다.
ex) 5는 1, 5에 의해서만 나누어지기 때문에 소수이다.
49는 아니다. 1, 7, 29가 존재하기 때문이다.
그러면 소수를 찾는 방법을 생각해 봅시다.
// 5000까지 소수를 찾는 방법
1. 모든 가능한 수로 나누어 보는 방법
쉽게 말해 어떤 수 P가 소수인지는 2부터 P-1까지 차례대로 나누어 보는 방법이다.
이 방법은 상당히 느린 방법이다. 많은 정수들을 일일이 다 확인해야 한다.
int N = 5000;
int isPrime( int i ) {
for( int j = 2; j < i; j++ ) {
if( i % j == 0 ) // j에 의해 나누어지면 소수가 아니다.
return 0;
}
return 1;
}
int main() {
for( int i = 2; i <= N; i++ ) {
if( isPrime(i) == 1 )
printf("%d ", i);
}
return 0;
}
2. 숫자의 특성을 이용하여
예를 들어 36이라는 숫자를 살펴보면
1 * 36
2 * 18
3 * 12
4 * 9
6 * 6
여기서 볼 수 있듯이 앞쪽의 숫자를 알면 뒷쪽의 숫자는 자동적으로 알 수 있다.
결국 n-1까지 체크할 필요없이
int N = 5000;
int isPrime( int i ) {
for( int j = 2; j*j <= i; j++ ) {
// 원래는
if( i % j == 0 )
return 0;
}
return 1;
}
int main() {
for( int i = 2; i <= N; i++ ) {
if( isPrime(i) == 1 )
printf("%d ", i);
}
return 0;
}
3. 짝수는 검사할 필요가 없다.
2를 제외한 짝수는 소수가 아니다. 홀수가 홀수에 의해 나누어지는지만 검사하면된다.
int N = 5000;
int isPrime( int i ) {
for( int j = 3; j*j <= i; j += 2 ) {
if( i % j == 0 ) //
return 0;
}
return 1;
}
int main() {
printf("2 ");
for( int i = 3; i <= N; i += 2 ) {
if( isPrime(i) == 1 )
printf("%d ", i);
}
return 0;
}
4. Sieve of Eratosthenes
어떤 숫자 b를 b보다 작은 소수들로 나누어지지 않으면 그것은 소수이다.
예를 들어 7은 소수이다. 왜냐하면 2, 3, 5로 나누어지지 않기 때문이다.
이것은 이전의 소수들만 체크하면 소수인지 아닌지 알 수 있다. 여기서 물론
이 아이디의 핵심은 배수들은 모두 버리는 것이다. 예를 들어 2가 소수이므로 배수인 4, 6,8... 은 버린다.
int N = 5000;
int status[5001];
int main() {
int i, j;
for( i = 2; i*i <= N; i++ ) {
if( status[i] == 0 ) {
for( j = 2 * i; j <= N; j += i )
status[j] = 1;
}
}
for( i = 2; i <= N; i++ ) {
if( status[i] == 0 ) {
printf("%d ", i);
}
}
return 0;
}
5. 4에서 다시 짝수는 검사를 할 필요가 없다.
int N = 5000;
int status[5001];
int main() {
int i, j;
for( i = 3; i <= N; i += 2 ) {
if( status[i] == 0 ) {
for( j = 3 * i; j <= N; j += 2 * i )
status[j] = 1;
}
}
printf("2 ");
for( i = 3; i <= N; i += 2 ) {
if( status[i] == 0 ) {
printf("%d ", i);
}
}
return 0;
}
6. 수정된 버리기 기술
n이 소수인지 판단할 때
int N = 5000, status[5001];
int main() {
int i, j;
for( i = 3; i*i <= N; i += 2 ) {
if( status[i] == 0 ) {
for( j = i * i; j <= N; j += i + i )
status[j] = 1;
}
}
printf("2 ");
for( i = 3; i <= N; i += 2 ) {
if( status[i] == 0 ) printf("%d ", i);
}
return 0;
}
7. 메모리까지 고려한다면 배열을 n개 필요없다.
이 부분은 여러분들을 위해 남겨두도록 하겠다.
