[백준 1929] 소수 구하기

#include<cstdio>
int main(void)
{
    int n,m,cnt;
    scanf("%d %d", &n, &m);
    for(int j=n; j<=m; j++) {
        cnt=0;
        for (int i=2; i<j; i++) {
            if (j%i == 0)
                cnt++;
        }
        if(cnt==0) printf("%d\n", j);
    }
    return 0;
}

이 방법으로 풀면 이중for문 때문에 시간이 오래 걸려서 시간초과가 발생한다.

에라토스테네스의 채를 이용해서 풀어야함.

bool은 전역으로 선언하면 0이기 때문에 false임.

#include<cstdio>
bool arr[1000002];
int main(void)
{
    int n,m;
    scanf("%d %d", &m, &n);
    arr[1]=true;
    for(int i=2; i<=n; i++)
        for(int j=2; i*j<=n; j++)
            arr[i*j]=true;
    
    for (int i=m; i<=n; i++)
        if(arr[i]==false)
            printf("%d\n", i);
    return 0;
}

#include<cstdio>
bool arr[1000002];
int main(void)
{
    int n,m;
    scanf("%d %d", &m, &n);
    arr[1]=true;
    
    for (int i = 2; i*i <= 1000000; i++) //2부터 1,000,000까지 체 돌리기
        if (arr[i] == false)
            for (int j = i * i; j <= 1000000; j += i) //배수 구하기
                arr[j] = true;
            
    for (int i=m; i<=n; i++)
        if(arr[i]==false)
            printf("%d\n", i);
    return 0;
}

위에껀 32ms, 아래껀 12ms 걸림