[알고리즘] 0 ~ N 사이의 소수 개수 구하기

 

코드 1 - i(2 ~ N)를 j(2 ~ i)로 나누기

 N을 입력받고 i를 2~N까지 1씩 더한다.

j가 2부터 i에 도달할때까지 1씩 더하면서 i와 나누어 떨어지면 (1과 자기 자신을 제외한 인수가 있으므로) 소수가 아님.

위 연산을 반복해서 0~N 까지 소수의 개수를 하나하나 판단하여 카운팅한다.

 

각 범위를 계산하며 시간을 측정해본 결과는 아래 표와 같다.

 

#include<stdio.h>
#include<math.h>

int main() {
    int i, j, cnt=0, flag=1;
    unsigned int min, max;

	// 범위 입력
    printf("min : ");
    scanf_s("%d", &min);
    printf("max : ");
    scanf_s("%d", &max);

	// 2보다 작은 최소 범위가 입력되면 2로 고정
    if (min < 2) min = 2;
	
    printf("입력 받은 범위 내의 소수");
    // i가 입력받은 최소 범위부터 최대 범위까지 반복
    for (i = min; i < max; i++) 
    {
        flag = 1; // 현재수가 소수라고 가정하고 시작
        
    	// j는 2부터 현재의 i 전까지 증가
        for (j = 2; j < i; j++) 
        {
        	// i와 j를 나눈 나머지가 존재하면 소수가 아님
            if (i % j == 0) 
            {
                flag = 0; // flag가 0이면 현재 수(i)는 소수가 아님
                break; // 더 이상 j로 나누어 줄 필요가 없으므로 탈출
            }
        }
		
        // 위에서 판단된 결과가 소수이면(0이 아니면)
        if (flag) 
        {
            cnt++; // 개수를 증가시킴 (입력 받은 범위 내의 소수 개수)
            printf("%d\t", i); // 출력
            
            if (cnt % 5 == 0) 
            {
            	printf("\n"); // 5개 단위로 끊음
            }
        }
    }

    printf("\n%d ~ %d 사이의 소수 개수 : %d개\n", min, max, cnt);

    return 0;
}

 

범위	개수	시간(s)
2~100	25	0.000s
2~1000	168	0.001s
2~10000	1229	0.028s
2~100000	9592	0.973s
2~1000000	78498	119.606s
2~10000000	-	-

 

---

 

코드 2 - i (2 ~ N)를 j (2 ~ i / j)로 나누기

 현재 수 i가 2의 배수일 경우 i/2 * 2 = i, 3의 배수일 경우 i/3 * 3 = i, 5와 7의 배수일 경우는 i/5 * 5 = i, i/7 * 7 = i 가 성립한다. (4, 6등은 2와 3의 배수이므로 해당 범위에 포함된다.)

위 공식을 일반화시키면 아래와 같고,

i/n * n = i

여기서 i의 소인수는 j와 i/j의 곱셈이므로 j는 i/j보다 클 수 없다는 가설을 적용하여 코드를 작성했다.

(수가 커질수록 더 많은 범위의 계산이 생략되므로 속도가 빨라짐)

아래 표를 보면 코드1의 방식보다 좀 더 개선된 걸 볼 수 있다.

 

#include<stdio.h>
#include<math.h>
#include<time.h>

void test(int min, int max) 
{
    clock_t start, end;
    float res;
    int i, j, cnt = 0, flag;

    start = clock();
    for (i = min; i < max; i++)
    {
        flag = 1;
		
        // 기존과 달라진 부분, j로 확인 하는 범위를 i와 현재 j의 나눈 몫까지로 줄였음
        for (j = 2; j <= (int)(i / j); j++)
        {
            if (i%j == 0)
            {
                flag = 0;
                break;
            }
        }

        if (flag)
        {
            cnt++;
        }
    }
    end = clock();

    res = (float)(end - start) / CLOCKS_PER_SEC;

    printf("%d~%d : %d개\t%.3fms\n", min, max, cnt, res);
}

int main() {
    int arr[] = {100, 1000, 10000, 100000, 1000000, 10000000, 1000000000};

    for (int i = 0; i < (int)(sizeof(arr) / sizeof(int)); i++)
    {
        test(2, arr[i]);
    }
    return 0;
}

 

범위	개수	시간(s)
2~100	25	0.000s
2~1000	168	0.000s
2~10000	1229	0.001s
2~100000	9592	0.028s
2~1000000	78498	0.359s
2~10000000	664579	7.392s
2~100000000	5761455	202.174s
2~1000000000	50847534	5087.694s
2~10000000000	-	-

 

---

 

코드 3 - 에라토스테네스의 체

 에라토스테네스의 체를 활용하여 미리 계산된 소수 여부 테이블을 참조하는 방식으로 개수 확인한다.

작은 범위에서는 위의 알고리즘 들과 비슷하거나 느리지만 큰 수의 범위로 가면 훨씬 빠른걸 볼 수 있다.

 

#include <iostream>

using namespace std;

typedef unsigned long long ll;

/*
* input : int m
* output : 1부터 m까지의 소수 여부를 sizeof(bool) * (m+1)크기의 bool * 형태로 반환한다.
* 사용 시 반환된 bool array에 해당 자연수를 조회하면 소수 여부를 알 수 있다.
*/
bool *Sieve_of_Eratosthenes(ll m) {
    bool* arr = new bool[m + 1];

    memset(arr, 1, sizeof(bool) * (m+1));
    arr[0] = false;
    arr[0] = false;

    for (ll i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (ll j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}

int main() {
    clock_t start, end;
    ll N, M;
    ll sum=0;

    start = clock();
    cin >> N >> M;
    bool* arr = Sieve_of_Eratosthenes(M);

    for (ll i = N; i <= M; i++) {
        if (arr[i]) {
            sum++;
        }
    }

    end = clock();
    float res = (float)(end - start) / CLOCKS_PER_SEC;
    cout << "" << N << " " << M << " " << sum << ", " << res << "ms" << endl;
    
    return 0;
}

범위	개수	시간(s)
2~100	25	7.149
2~1000	168	9.231
2~10000	1229	14.213
...	-	-
2~100000000	5761455	53.387
2~1000000000	50847534	23.744
2~10000000000	455052511	252.08
2~100000000000	-	-

 

---

 

참고

• 계산 범위의 조절로 100만에서 1억으로 향상되었지만 여전히 큰 수를 처리하기엔 어려움
• 에라토스테네스의 체를 활용할 경우 테이블 생성으로 인해 작은 수 범위에서는 더 오래걸리지만,
  큰 수에서는 훨씬 적은 시간이 걸림. (1억에서 100억 단위로 향상됨)
• Openssl을 활용한 더 큰 소수의 활용은 아래 블로그에 있다.

https://nitwit.tistory.com/17

암호학 - 소수 판별