#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <bits/stdc++.h> #include "../../Math/Number-Theory/eratosthenes-sieve.hpp" #include "../../Math/Number-Theory/is-prime.hpp" constexpr int N = 1e4; EratosthenesSieve sieve(N); void test_isPrime() { for (int i = 0; i <= N; ++i) { assert(sieve.isPrime(i) == isPrime(i)); } std::clog << __func__ << " : OK" << std::endl; } void test_minFactor() { const auto minFactor = [](int n) { if (n % 2 == 0) return 2; for (int i = 3; i < n; ++i) if (n % i == 0) return i; return -1; }; for (int i = 2; i <= N; ++i) { if (sieve.isPrime(i)) { assert(sieve.minFactor(i) == i); } else { assert(sieve.minFactor(i) == minFactor(i)); } } std::clog << __func__ << " : OK" << std::endl; } int main() { std::cout << "Hello World" << std::endl; test_isPrime(); test_minFactor(); return 0; }
#line 1 "test/helloworld/eratosthenes-sieve.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <bits/stdc++.h> #line 5 "Math/Number-Theory/eratosthenes-sieve.hpp" /** * @brief Eratosthenes-Sieve (エラトステネスの篩) * @see https://qiita.com/rsk0315_h4x/items/ff3b542a4468679fb409 */ class EratosthenesSieve { private: int m_size; std::vector<int> m_minFactor; public: EratosthenesSieve() = default; //! [0, n] の範囲で篩を構築する explicit EratosthenesSieve(int n_) : m_size(n_ + 1) , m_minFactor(m_size) { std::iota(m_minFactor.begin(), m_minFactor.end(), 0); for (int i = 2; i * i < m_size; ++i) { if (m_minFactor[i] < i) continue; for (int j = i * i; j < m_size; j += i) { if (m_minFactor[j] == j) m_minFactor[j] = i; } } m_minFactor[0] = -1; if (n_ >= 1) m_minFactor[1] = -1; } bool isPrime(int x) const { assert(0 <= x && x < m_size); return m_minFactor[x] == x; } int minFactor(int x) const { assert(0 <= x && x < m_size); return m_minFactor[x]; } }; #line 3 "Math/Number-Theory/is-prime.hpp" /** * @brief isPrime() (素数判定 $O(\sqrt n)$) */ constexpr bool isPrime(int64_t n) { if (n == 2) return true; if (n <= 1 || n % 2 == 0) return false; for (int64_t i = 3; i * i <= n; i += 2) { if (n % i == 0) return false; } return true; } #line 6 "test/helloworld/eratosthenes-sieve.test.cpp" constexpr int N = 1e4; EratosthenesSieve sieve(N); void test_isPrime() { for (int i = 0; i <= N; ++i) { assert(sieve.isPrime(i) == isPrime(i)); } std::clog << __func__ << " : OK" << std::endl; } void test_minFactor() { const auto minFactor = [](int n) { if (n % 2 == 0) return 2; for (int i = 3; i < n; ++i) if (n % i == 0) return i; return -1; }; for (int i = 2; i <= N; ++i) { if (sieve.isPrime(i)) { assert(sieve.minFactor(i) == i); } else { assert(sieve.minFactor(i) == minFactor(i)); } } std::clog << __func__ << " : OK" << std::endl; } int main() { std::cout << "Hello World" << std::endl; test_isPrime(); test_minFactor(); return 0; }