[알고리즘 필수] 소수 구하기

ㅅ

 

1. 소수 찾기 : 에라토스테네스의 체를 사용한다.

단, 메모리 초과 유의 (10^6 까지 안전 - 128 MB 제한 기준 )

bool isPrime[4000004];
vector<int> v;

void go(int n)
{
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = false, isPrime[1] = false;
    for (int i = 2; i * i <= n; i++)
    {
        if (isPrime[i])
        {
            for (int j = 2; i * j <= n; j++)
            {
                isPrime[i * j] = false;
            }
        }
    }
}

 

2. 소수 찾기 : 완전 탐색 (for문) 

bool check(int num)
{
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}