문제
1에서 30만까지의 범위 중 소수를 구해 출력하세요.
소수의 정의
1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수
ex) 2, 3, 4, 5, 7, 11, 13, 17, 23...
1. 한 번씩 모두 나눠보기
소수이기 위해서는 내가 구하고자 하는 수(n)가 1보다 크고 n보다 작은 수로 나눠지지 않으면 된다. 즉, n이 2에서 n-1까지의 수로 나눠지는지 확인해보면 된다. 나누었을 때 나눠 떨어진다면 약수가 있다는 뜻이므로 소수가 될 수 없다.
- 시간복잡도 : O(n^2)
#include <stdio.h>
int main(){
int n, i;
int isPrime; //0이면 소수가 아님, 1이면 소수
unsigned long counter = 0; //실행 횟수
for(n=2; n<=10000; n++){
isPrime = 1;
for(i=2; i<n; i++){
counter++;
if (n%i == 0){ //나누어 떨어짐.
isPrime = 0; //소수가 아니다.
break;
}
}
if(isPrime){ //소수이면
printf("%d ", n);
}
}
printf("\n실행횟수 : %lu\n", counter);
return 0;
}
2. 절반까지만 나눠보기
예를 들어 16(n=16)이 소수인지 판별한다고 가정하자.
그렇다면 1과 16사이의 모든 수 (2~15)로 나눠볼 것이다.
맨 처음에 2로 나누면 16 = 2 * 8이 된다. 이것은 동시에 16 = 8 * 2를 의미하므로 8로 나누는 것과 동일하다.
n이 다른 숫자인 경우도 동일하다. n이 90인 경우 90 = 2 * 45인것과 동시에 90 = 45 * 2이다.
이처럼 n의 절반인 수 이상으로 나눠보는 것은 의미가 없다는 것을 알 수 있다. 45가 최소의 수 약수인 2를 가질 수 있는 최대치이므로 45미만의 수 까지만 나눠봐도 된다.
그렇다면 n이 홀수인 경우에는 어떻게 해야할까? 9가 소수인지 판별해볼 때 9의 절반이 되는 수는 4.5이다. 4.5라는 수는 자연수가 아니므로 이때는 4까지만 나눠보면 된다.
- 시간복잡도 : O(n^2)
#include <stdio.h>
int main(void){
int n, i;
int isPrime; //0이면 소수가 아님, 1이면 소수
unsigned long counter = 0; //실행 횟수
for(n=2; n<=10000; n++){
isPrime = 1;
for(i=2; i<=n/2; i++){
counter++;
if (n%i == 0){ //나누어 떨어짐.
isPrime = 0; //소수가 아니다.
break;
}
}
if(isPrime){ //소수이면
printf("%d ", n);
}
}
printf("\n실행횟수 : %lu\n", counter);
return 0;
}
3. 홀수만을 대상으로 하며 이미 얻은 소수로 나눠보기
2를 제외한 짝수의 경우 모두 2를 약수로 가지므로 소수가 될 수 없다.
짝수를 일일이 확인해 나눠보는 것은 의미가 없으므로 홀수만을 대상으로 한다.
1부터 n-1까지 한 번씩 나눠보는 것 보다는 이미 얻은 소수로 n을 나누는 것이 훨씬 효율적이다.
int main(void){
int i, n;
int prime[5000]; //소수를 저장하는 배열
int ptr = 0; //이미 얻은 소수의 개수
unsigned long counter = 0; //나눗셈 횟수
prime[ptr++] = 2; //2는 소수
for (n = 3; n <= 10000; n += 2){ //홀수만을 대상으로 한다.
for(i = 1; i < ptr; i++) {
counter ++;
if(n % prime[i] == 0) //이미 얻은 소수로 나눈다.
break;
}
if(ptr == i) //마지막까지 나누어떨어지지 않았다면
prime[ptr++] = n; // 소수를 배열에 저장한다.
}
for (i = 0; i < ptr; i++)
printf("%d ", prime[i]);
printf("\n실행횟수 : %lu\n", counter);
return 0;
}
4. 제곱근까지만 나눠 보기
36(n=36)을 소수인지 판별한다고 가정하자.
36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36 이다.
이 약수들은 제곱근을 기점으로 서로 대응이 된다.
2*18=36, 18*2=36 과 같은 방법으로 1, 2, 3, 4, 5, 6은 9, 12, 18, 36과 대응이 된다.
대응되는 약수 : (2, 18), (3, 12), (4, 9), (6, 6)
제곱근이 자연수가 아닌 경우, 예를 들어 n이 10일 때에는 10의 제곱근 전까지만 나눠보면 된다. 10의 제곱근은 3.1622이므로 3까지만 나눠보면 된다.
- 시간복잡도 : O(N√N)
#include <stdio.h>
#include <math.h>
int main(){
int n, i;
int isPrime; //0이면 소수가 아님, 1이면 소수
unsigned long counter = 0; //실행 횟수
for(n=2; n<=10000; n++){
isPrime = 1;
for(i=2; i <= sqrt(n); i++){
counter++;
if (n%i == 0){ //나누어 떨어짐.
isPrime = 0; //소수가 아니다.
break;
}
}
if(isPrime){ //소수이면
printf("%d ", n);
}
}
printf("\n실행횟수 : %lu\n", counter);
return 0;
}5. 에라토스테네스의 체
에라토스테네스의 체란?
그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수를 찾는 방법이다.
입자의 크기가 서로 다른 가루들을 섞어 체에 거르면 특정 크기 이하의 가루들은 다 아래로 떨어지고, 그 이상의 것들만 체 위에 남는 것처럼, 에라토스테네스의 체를 사용하면 특정 자연수 이하의 합성수는 다 지워지고 소수들만 남는 것이다.
주어진 숫자들을 모두 나열하고 1을 제외한 숫자를 소수라고 가정한다.
나열된 숫자들 중 소수이면서 가장 작은 숫자부터 시작해서 그 숫자의 배수들을 모두 지운다. 이는 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하였다.
이렇게 2부터 n까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별한다.
제곱근 까지만 나눴던 방법처럼 소수인지 확인하려면 2부터 루트 n까지 for문을 돌리면서 특정 숫자의 제곱근 까지만 약수의 여부를 검증한다.
- 시간복잡도 : O(Nlog(logN))
#include <stdio.h>
#include <math.h>
#define MAX 10000
int main()
{
char isPrime[MAX+1]; //소수를 체크하기 위한 배열, 0번째 건너띄고 1번째 인덱스부터 사용
isPrime[1] = 0; //1은 소수가 아니라고 가정
unsigned long counter = 0; //실행 횟수
//1외에는 모두 소수라고 가정
for (int i = 2; i < MAX+1; i++)
{
isPrime[i] = 1;
}
//에라토스테네스의 체
for (int n = 2; n <= floor(sqrt(MAX)); n++)
{
if (!isPrime[n]) //n이 소수가 아닌 경우
{
continue;
}
//소수인 n의 배수들 모두 제거
for (int mult = 2; counter++, n * mult <= MAX; mult++) {
counter++;
isPrime[n*mult] = 0;
}
}
//에라토스테네스의 체를 이용하여 남은 소수들 출력
for (int i = 1; i < MAX+1; i++)
{
if (isPrime[i])
{
printf("%d ", i);
}
}
printf("\n실행횟수 : %lu\n", counter);
return 0;
}
참고)
