(정수론/C) 2억 이하 소수 개수 구하기

// 파이썬으로 소수를 구하는 데 시간이 많이 걸려서 C언어로 코드를 짜서 2억(200,000,000)까지의 
// 소수 개수를 세어보았다.
// 먼저 1억까지 세고 나서 2억을 셌는데, 실행 결과는 1억의 경우를 적었다.

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

// num의 약수를 모두 구해서 화면에 출력한다.
// getDivisor (100) => 1  2  4  5  10  20  25  50  100
// 입력 자료형, 반환 자료형 등은 모두 큰 숫자를 저장할 수 있는 long int로 하고 출력 서식은 %ld로 한다.
unsigned long getDivisor (unsigned long num) {
    printf("%ld의 약수: \n", num);
    for (int i = 1; i <= sqrt(num); i++) {
        if (num % i == 0)
            printf("(%d  %ld)\n", i, num / i);
    }
    printf("\n");
    return 0;
}

// 어떤 수가 소수인지 아닌지 판단한다. 그 수를 그 수의 루트까지로 나눠봐서 나눠지면 소수, 
// 아니면 소수가 아니다.
// 소수이면 1(true), 아니면 0(false)
unsigned long isPrime(unsigned long num) {
    for (int i = 2; i <= sqrt(num); i++)
        if (num % i == 0) return 0;
    return 1;
}

// num까지의 소수를 모두 출력한다.
// num: 이하의 소수를 구할 숫자.
// getCountOnly: 0이면 소수를 출력하고 갯수도 구한다. 1이면 소수를 출력하지 않고 갯수만 구한다.
unsigned long getPrimes(unsigned long num, int getCountOnly) {
    unsigned long count = 0;
    for (unsigned long i = 2; i <= num; i++) {
        if(isPrime(i)) {  //소수면 출력하거나 개수를 하나 올린다.
            if (!getCountOnly) {
                printf("%ld  ", i);
            }
            count++;
        }
    }
    return count;
}

int main() {
    //unsigned long num1 = 4294145925;
    unsigned long num1 = 143;
    unsigned long num2 = 2147483647;
    unsigned long num3 = 1234567891;
    unsigned long count = 0;

    getDivisor(100); // 100의 약수들 구하기

    if (isPrime(num1)) {
        printf("%ld는 소수입니다.\n", num1);
    }
    else {
        printf("%ld는 소수가 아닙니다.\n", num1);
        getDivisor(num1);
    }

    if (isPrime(num2)) {
        printf("%ld는 소수입니다.\n", num2);
    }
    else {
        printf("%ld는 소수가 아닙니다.\n", num2);
        printf("\n");
        getDivisor(num2);
    }

    if (isPrime(num3)) {
        printf("%ld는 소수입니다.\n", num3);
    }
    else {
        printf("%ld는 소수가 아닙니다.\n", num3);
        getDivisor(num3);
    }

    printf("\n");
    
    unsigned long int num = 100000000;
    count = getPrimes(num, 1);
    printf("\n%ld 이하의 소수 개수: %ld 개\n", num, count);

    return 0;
}

실행 결과:

$ gcc getPrimes.c -lm; ./a.out

100의 약수: 
(1  100)
(2  50)
(4  25)
(5  20)
(10  10)

143는 소수가 아닙니다.
143의 약수: 
(1  143)
(11  13)

2147483647는 소수입니다.
1234567891는 소수입니다.


100000000 이하의 소수 개수: 5761455 개

----------------------------------------

아래는 '친절한 수론 길라잡이' 13장 '소수 세기' 비교 표를 참고해서 직접 실행해보고 작성한 표이다.