[C/C++] 소수 구하기 - 에라토스테네스의 체

#include <stdio.h>
#include <stdlib.h>

void eratos_sieve(int n, char* primes)  // primes size = n + 1
{
    int i, j;
    
    for (i = 2; i <= n; i++)
        primes[i] = 1;

    for (i = 2; i * i <= n; i++)
        if (primes[i])
            for (j = i * i; j <= n; j += i)
                primes[j] = 0;    
}

int main()
{
    int i, j, n = 100000000;
    char* primes = (char*)malloc(n + 1);  // 체 공간 할당
    
    eratos_sieve(n, primes);
   
    for (i = 2, j = 0; i < n && j < 10; i++)  // 작은 순서로 10개 출력
        if (primes[i])
            printf("%d\n", i), ++j;

    for (i = n, j = 0; i >= 2 && j < 10; i--)  // 큰 순서로 10개 출력
        if (primes[i])
            printf("%d\n", i), ++j;

    free(primes);
}

 

시간복잡도는 O(n) 과 큰차이 없는 O(n * log(log(n)) 라고 한다.

계산횟수에서 log 의 밑은 π에 가깝다.