[백준 1929] 소수 구하기, C++

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

  본 문제는 소수 구하기 문제인데 입력 값이 1,000,000이다. 소수를 판단하는 알고리즘은

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

에라토스테네스의 체

#include <cstdio>
 
using namespace std;
 
int main() {
    bool chk[1000001];
    int n, m, cnt = 0;
    for (int i = 2; i <= 1000000; i++) {
        if (!chk[i]) {
            cnt += 1;
            for (int j = i*2; j <= 1000000; j += i) {
                chk[j] = true;
            }
        }
    }
    chk[0] = true;
    chk[1] = true;
    scanf("%d %d", &n, &m);
    for (int i = n; i <= m; i++) {
        if (!chk[i]) {
            printf("%d", i);
            if (i != m-1) printf("\n");
        }
    }
}

 

느린 방법

#include <iostream>
 
using namespace std;
 
bool prime(int n) {
    if (n < 2)
        return false;
    for (int i = 2; i*i <= n; i++){
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}
 
int main() {
    int n, m;
 
    cin >> n >> m;
 
    for (n; n <= m; n++) {
        if (prime(n)) {
            cout << n << '\n';
        }
    }
}