Prime

소수 구하기

소수 구하기

1 <= i < sqrt(n) 에서, n % i == 0 이면 i 와 n/i 는 소수

i * i == n 이면, i 는 소수

// 코드 짜기가 귀찮습ㄴ다.

에라토스테네스의 체

#include <stdio.h>

int main()
{
    int prime[100001] = {1, 1}, i, j;

    for ( i = 2; i <= 100000; i++ )
        if ( prime[i] == 0 )
            for ( j = i+i; j <= 100000; j+=i )
                prime[j] = 1;

    return 0;
}