verify/aoj_alds1/aoj_alds1_1_c_osa_k.test.cpp

• View this file on GitHub
• Last update: 2023-02-06 23:12:05+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C

Depends on

• math/osak.hpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C"

#include <bits/stdc++.h>

#include "math/osak.hpp"

int main() {
    auto osak = Osak(100000000);
    int n;
    std::cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        ans += osak.is_prime(a);
    }
    std::cout << ans << '\n';
    return 0;
}

#line 1 "verify/aoj_alds1/aoj_alds1_1_c_osa_k.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C"

#include <bits/stdc++.h>

#line 2 "math/osak.hpp"

struct Osak {
    int n;
    std::vector<int> min_factor;

    Osak(int n) : n(n), min_factor(n + 1) {
        std::iota(min_factor.begin(), min_factor.end(), 0);
        if (n >= 0) min_factor[0] = -1;
        if (n >= 1) min_factor[1] = -1;
        for (int p = 2; p * p <= n; p++) {
            if (min_factor[p] != p) continue;
            for (int i = p * p; i <= n; i += p) {
                if (min_factor[i] != i) continue;
                min_factor[i] = p;
            }
        }
    }

    bool is_prime(int x) {
        assert(x <= n);
        return min_factor[x] == x;
    }

    std::map<int, int> prime_factor(int x) {
        assert(x <= n);
        std::map<int, int> pf;
        while (x > 1) {
            pf[min_factor[x]]++;
            x /= min_factor[x];
        }
        return pf;
    }
};
#line 6 "verify/aoj_alds1/aoj_alds1_1_c_osa_k.test.cpp"

int main() {
    auto osak = Osak(100000000);
    int n;
    std::cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        ans += osak.is_prime(a);
    }
    std::cout << ans << '\n';
    return 0;
}

Back to top page