[백준 1929] 소수 구하기(DP문제)

음... 옛날에 저 에라토스테네스의 체 를 본적이 있어가지고 금방 푼 것 같다.

그냥 IsPrime만 돌리면 시간초과 바로 나버리니 dp로 풀어야함.

#include <bits/stdc++.h>

using namespace std;


uint8_t prime[1000001];

bool IsPrime(int a){
    bool flag = true;

    for(int i =a-1 ; i>1; i--)
    {
        if(a%i ==0){
            return false;
        }
    }
    return true;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    //아직 미탐색 0, prime num = 1, 소수 아니면 2.
    prime[1]=2;
    for(int i =2; i<=1000000;i++){
        if(prime[i] ==0){
            if(IsPrime){
                prime[i] =1; //처음 탐색했는데 소수면 1 표시해놓고
                int cnt =2; 
                while(1)
                {
                    if(i*cnt>1000000) break;
                    prime[i *cnt] =2; // 그 소수에 *2, *3,*4들은 다 소수가 아니므로 2로 체크함.
                    cnt++;
                }
            } 
            else prime[i] = 2; // 소수가 아니면 2
        }   
    }
    for(int i = N; i<=M; i++)
    {
        if(prime[i] ==1) cout << i << '\n';
    }
}