test/math/eratosthenes_sieve.test.cpp

• View this file on GitHub
• Last update: 2023-08-23 17:33:30+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C

Depends on

• Eratosthenes Sieve (math/eratosthenes_sieve.hpp)

Code

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

#include "../../math/eratosthenes_sieve.hpp"


#include <iostream>


int main() {
    int n;
    std::cin >> n;
    ebi::eratosthenes_sieve sieve(1e8);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int p;
        std::cin >> p;
        if (sieve.is_prime(p)) ans++;
    }
    std::cout << ans << '\n';
}

#line 1 "test/math/eratosthenes_sieve.test.cpp"
#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C"

#line 2 "math/eratosthenes_sieve.hpp"

#include <cassert>

#include <cstdint>

#include <vector>


/*
    reference: https://37zigen.com/sieve-eratosthenes/
*/

namespace ebi {

struct eratosthenes_sieve {
  private:
    using i64 = std::int_fast64_t;
    int n;
    std::vector<bool> table;

  public:
    eratosthenes_sieve(int _n) : n(_n), table(std::vector<bool>(n + 1, true)) {
        table[1] = false;
        for (i64 i = 2; i * i <= n; i++) {
            if (!table[i]) continue;
            for (i64 j = i; i * j <= n; j++) {
                table[i * j] = false;
            }
        }
    }

    bool is_prime(int p) {
        return table[p];
    }

    std::vector<int> prime_table(int m = -1) {
        if (m < 0) m = n;
        std::vector<int> prime;
        for (int i = 2; i <= m; i++) {
            if (table[i]) prime.emplace_back(i);
        }
        return prime;
    }
};

}  // namespace ebi
#line 5 "test/math/eratosthenes_sieve.test.cpp"

#include <iostream>


int main() {
    int n;
    std::cin >> n;
    ebi::eratosthenes_sieve sieve(1e8);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int p;
        std::cin >> p;
        if (sieve.is_prime(p)) ans++;
    }
    std::cout << ans << '\n';
}

Back to top page