[백준 1978] 소수 찾기

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

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 n, num;
    cin >> n;
    int ans = 0;
    while (n--) {
        cin >> num;
        if (num == 1) continue;

        bool isPrime = true;
        for (int i = 2; i < num; ++i) { // num - 1까지 다 돌기
            if (num % i == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) ++ans;
    }
    cout << ans;

    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 n, num;
    cin >> n;
    int ans = 0;
    while (n--) {
        cin >> num;
        if (num == 1) continue;

        bool isPrime = true;
        for (int i = 2; i <= (int) sqrt(num); ++i) {
            if (num % i == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) ++ans;
    }
    cout << ans;

    return 0;
}

 

3. 에라토스테네스의 체

#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; }
bool isPrime[1001] = { 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 < 1001; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j < 1001; j += i) {
                isPrime[j] = false;
            }
        }
    }
    int n, num;
    cin >> n;
    int ans = 0;
    while (n--) {
        cin >> num;
        if (isPrime[num]) ans++;
    }
    cout << ans;

    return 0;
}