tests/math/prime_enumerate.test.cpp

View this file on GitHub
Last update: 2024-04-03 22:46:30+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_1_C

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_1_C"

#include <bits/stdc++.h>
#include "ugilib/base/constants.hpp"
#include "ugilib/base/definitions.hpp"
#include "ugilib/math/primes.hpp"

using namespace std;

// debug settings
// #define DEBUG
#ifdef DEBUG
// debug input
string _INPUT = R"(
5
1 2 3 4 5
)";
auto _cin = stringstream(_INPUT.substr(1)); // remove '\n' at _INPUT[0]
#else
// standard input
auto& _cin = cin;
#endif

// speed up
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// reader
struct rd {
    // T
    template<typename T> static T i() { T x; _cin >> x; return x; }  // T item
    // vector<T>
    template<typename T> static vector<T> v(int n) {vector<T> v(n); rep(i, n) _cin >> v[i]; return v;}  // vector<T>
    // vector<pair<T, T>>
    template<typename T> static vector<pair<T, T>> vp(int n) {vector<pair<T, T>> v(n); rep(i, n) _cin >> v[i].first >> v[i].second; return v;}  // vector<pair<T, T>>
    // tuple
    template<typename... Args> static tuple<Args...> t() {
        tuple<Args...> values;
        apply([](auto&... args) { ((_cin >> args), ...); }, values);
        return values;
    }
};

// debug print utility
namespace deb {
    #include <cxxabi.h>
    // demangle type name
    string demangle(const char* name) {
        int status = -4;
        unique_ptr<char, void(*)(void*)> res{
            abi::__cxa_demangle(name, NULL, NULL, &status),
            free
        };
        return (status == 0) ? string(res.get()) : name ;
    }
    // meta functions for type traits
    template<typename T>
    constexpr bool isArithmeticContainer() { return is_arithmetic<typename T::value_type>::value; }
    // for SFINAE
    template<typename T, typename = void> struct has_key_and_mapped_type : false_type {};
    template<typename T> struct has_key_and_mapped_type<T, void_t<typename T::key_type, typename T::mapped_type>> : true_type {};
    // for map or unordered_map
    template<typename T>
    constexpr bool isMapLike() { return has_key_and_mapped_type<T>::value; }

    // for values
    template<typename T, typename enable_if<is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& x) { cout << x << " "; }
    // for pairs
    template <typename T, typename S>
    void p(const pair<T, S>& _p){ p(_p.first); p(_p.second); cout << endl; }
    // for containers
    template<typename T,  typename enable_if<!is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& container) {
        // map and unordered_map
        if constexpr (isMapLike<T>()) {
            cout << demangle(typeid(T).name()) << ":" << endl;
            for (const auto& kv : container) {
                cout << "[" << kv.first << "] => ";
                p(kv.second);
                if constexpr (is_arithmetic_v<typename T::mapped_type>) cout << endl;
            }
        // vector or set or others
        } else {
            if constexpr (!isArithmeticContainer<T>()) cout << demangle(typeid(T).name()) << ":" << endl;
            for (auto it = begin(container); it != end(container); ++it) {
                p(*it);
            }
            if constexpr (isArithmeticContainer<T>()) cout << endl;
        }
    }
};  // namespace deb

int main() {
    auto& cin = _cin;
    // speed up io
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    // code
    int n = rd::i<int>();
    vector<ll> queries = rd::v<ll>(n);
    ll max = *max_element(queries.begin(), queries.end());
    auto primes = ugilib::shieve(ll(sqrt(max))+2);

    ll ans = 0;
    unordered_set<ll> prime_set(primes.begin(), primes.end());
    for (ll q : queries) {
        if (prime_set.count(q)) ans++;
        else {
            bool is_prime = true;
            for (ll p : primes) {
                if (q % p == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

#line 1 "tests/math/prime_enumerate.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_1_C"

#include <bits/stdc++.h>
#line 2 "ugilib/base/definitions.hpp"

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i, n) for(size_t i = 0; i < n; i++)  // rep macro
#define all(v) begin(v), end(v)  // all iterator
#line 3 "ugilib/base/constants.hpp"

namespace ugilib::constants {
    template<typename T>
    inline constexpr T INF = std::numeric_limits<T>::max() / 2;
} // namespace ugilib::constants

const ll INF = ugilib::constants::INF<ll>;
#line 3 "ugilib/math/primes.hpp"
using namespace std;

namespace ugilib {
    /**
     * @brief エラトステネスの篩
     * @tparam T 整数型
     * @param n 素数の上限. nを含む
     * @return vector<T> 素数リスト
     * @note O(n log log n)
     * @note jに代入される数の最大値はN^2なのでオーバーフローに注意
    */
    template <typename T>
    vector<T> shieve(const T &n) {
        vector<bool> is_prime(n + 1, true);
        vector<T> primes;
        is_prime[0] = is_prime[1] = false;
        for (T i = 2; i <= n; i++) {
            if (!is_prime[i]) continue;
            primes.push_back(i);
            for (T j = i * i; 0 <= j && j <= n; j += i) {  // オーバーフローに注意
                is_prime[j] = false;
            }
        }
        return primes;
    }

    /**
     * @brief 素因数分解. 素数リストを用いる
     * @tparam T 整数型
     * @param n 素因数分解する数
     * @param primes 素数リスト. shieveで取得したものを使う
     * @return vector<pair<T, int>> 素因数とその個数
     * @note O(sqrt(n)) より高速. shieveに時間がかかり，メモリをより消費する
    */
    template <typename T>
    vector<pair<T, int>> prime_factorization_with_shieve(T n, const vector<T>& primes) {
        vector<pair<T, int>> factors;  // 素因数とその個数
        for (const T &p : primes) {
            if (p * p > n) break;
            if (n % p != 0) continue;
            int count = 0;
            while (n % p == 0) {
                n /= p;
                count++;
            }
            factors.push_back({p, count});
        }
        if (n != 1) factors.push_back({n, 1});  // nが素数の場合
        return factors;
    }

    /**
     * @brief 素因数分解
     * @tparam T 整数型
     * @param n 素因数分解する数
     * @return vector<pair<T, int>> 素因数とその個数
     * @note O(sqrt(n))
    */
    template <typename T>
    vector<pair<T, int>> prime_factorization(T n) {
        vector<pair<T, int>> factors;
        for (T i = 2; i * i <= n; i++) {
            if (n % i != 0) continue;
            int count = 0;
            while (n % i == 0) {
                n /= i;
                count++;
            }
            factors.push_back({i, count});
        }
        if (n != 1) factors.push_back({n, 1});  // nが素数の場合
        return factors;
    }
} // namespace ugilib
#line 7 "tests/math/prime_enumerate.test.cpp"

using namespace std;

// debug settings
// #define DEBUG
#ifdef DEBUG
// debug input
string _INPUT = R"(
5
1 2 3 4 5
)";
auto _cin = stringstream(_INPUT.substr(1)); // remove '\n' at _INPUT[0]
#else
// standard input
auto& _cin = cin;
#endif

// speed up
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// reader
struct rd {
    // T
    template<typename T> static T i() { T x; _cin >> x; return x; }  // T item
    // vector<T>
    template<typename T> static vector<T> v(int n) {vector<T> v(n); rep(i, n) _cin >> v[i]; return v;}  // vector<T>
    // vector<pair<T, T>>
    template<typename T> static vector<pair<T, T>> vp(int n) {vector<pair<T, T>> v(n); rep(i, n) _cin >> v[i].first >> v[i].second; return v;}  // vector<pair<T, T>>
    // tuple
    template<typename... Args> static tuple<Args...> t() {
        tuple<Args...> values;
        apply([](auto&... args) { ((_cin >> args), ...); }, values);
        return values;
    }
};

// debug print utility
namespace deb {
    #include <cxxabi.h>
    // demangle type name
    string demangle(const char* name) {
        int status = -4;
        unique_ptr<char, void(*)(void*)> res{
            abi::__cxa_demangle(name, NULL, NULL, &status),
            free
        };
        return (status == 0) ? string(res.get()) : name ;
    }
    // meta functions for type traits
    template<typename T>
    constexpr bool isArithmeticContainer() { return is_arithmetic<typename T::value_type>::value; }
    // for SFINAE
    template<typename T, typename = void> struct has_key_and_mapped_type : false_type {};
    template<typename T> struct has_key_and_mapped_type<T, void_t<typename T::key_type, typename T::mapped_type>> : true_type {};
    // for map or unordered_map
    template<typename T>
    constexpr bool isMapLike() { return has_key_and_mapped_type<T>::value; }

    // for values
    template<typename T, typename enable_if<is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& x) { cout << x << " "; }
    // for pairs
    template <typename T, typename S>
    void p(const pair<T, S>& _p){ p(_p.first); p(_p.second); cout << endl; }
    // for containers
    template<typename T,  typename enable_if<!is_arithmetic<T>::value, nullptr_t>::type = nullptr>
    void p(const T& container) {
        // map and unordered_map
        if constexpr (isMapLike<T>()) {
            cout << demangle(typeid(T).name()) << ":" << endl;
            for (const auto& kv : container) {
                cout << "[" << kv.first << "] => ";
                p(kv.second);
                if constexpr (is_arithmetic_v<typename T::mapped_type>) cout << endl;
            }
        // vector or set or others
        } else {
            if constexpr (!isArithmeticContainer<T>()) cout << demangle(typeid(T).name()) << ":" << endl;
            for (auto it = begin(container); it != end(container); ++it) {
                p(*it);
            }
            if constexpr (isArithmeticContainer<T>()) cout << endl;
        }
    }
};  // namespace deb

int main() {
    auto& cin = _cin;
    // speed up io
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    // code
    int n = rd::i<int>();
    vector<ll> queries = rd::v<ll>(n);
    ll max = *max_element(queries.begin(), queries.end());
    auto primes = ugilib::shieve(ll(sqrt(max))+2);

    ll ans = 0;
    unordered_set<ll> prime_set(primes.begin(), primes.end());
    for (ll q : queries) {
        if (prime_set.count(q)) ans++;
        else {
            bool is_prime = true;
            for (ll p : primes) {
                if (q % p == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) ans++;
        }
    }

    cout << ans << endl;

    return 0;
}