[백준 2581] 소수

정답 코드를 바로 보기보다는 아래 글을 먼저 읽고 푸시길 바랍니다.

https://pushback.tistory.com/8

소수 문제 해결의 기본

---

1. naive

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int M, N;
    cin >> M >> N;

    int sum = 0, min_prime = 10001;
    for (int cur = M; cur <= N; ++cur) {
        if (cur == 1) continue;

        bool isPrime = true;
        for (int div = 2; div < cur; ++div) {
            if (cur % div == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            sum += cur;
            min_prime = min(min_prime, cur);
        }
    }
	
    if (sum == 0) cout << -1;
    else cout << sum << '\n' << min_prime;
	

    return 0;
}

 

2. naive(개선)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int M, N;
    cin >> M >> N;

    int sum = 0, min_prime = 10001;
    for (int cur = M; cur <= N; ++cur) {
        if (cur == 1) continue;

        bool isPrime = true;
        for (int div = 2; div <= (int)sqrt(cur); ++div) {
            if (cur % div == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            sum += cur;
            min_prime = min(min_prime, cur);
        }
    }
	
    if (sum == 0) cout << -1;
    else cout << sum << '\n' << min_prime;
	

    return 0;
}

 

3. 에라토스테네스의 체

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 10e+4 + 1;
const int MOD = 1e+9;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

bool isPrime[10001] = { 0, };
int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[1] = false;
    for (int i = 2; i < 10001; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j < 10001; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    int M, N;
    cin >> M >> N;
    int sum = 0, min_prime = 10001;
    for (int cur = M; cur <= N; ++cur) {
        if (isPrime[cur]) {
            sum += cur;
            min_prime = min(min_prime, cur);
        }
    }
    if (sum == 0) cout << -1;
    else cout << sum << '\n' << min_prime;

    return 0;
}