test/Sieve.test.cpp

• View this file on GitHub
• Last update: 2021-03-21 09:59:09+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_1_C

Depends on

• math/Sieve.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_1_C"
#include "./../math/Sieve.cpp"
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	Sieve sieve(100000000);
	const auto& primes = sieve.primes();
	int n;
	cin >> n;
	int ans = 0;
	while (n--) {
		int x;
		cin >> x;
		ans += sieve.is_prime(x);
		assert(sieve.is_prime(x) == binary_search(primes.begin(), primes.end(), x));
	}
	cout << ans << '\n';
}

#line 1 "test/Sieve.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_1_C"
#line 2 "math/Sieve.cpp"
#include <vector>
#include <map>
#include <utility>
#include <cassert>

class Sieve {
	int n;
	std::vector<int> factor_m, primes_m;

public:
	Sieve(int _n) : n(_n), factor_m(_n + 1) {
		assert(1 <= n);
		factor_m[0] = factor_m[1] = -1;
		for (long long i = 2; i <= n; ++i) {
			if (!factor_m[i]) {
				primes_m.push_back(i);
				factor_m[i] = i;
				for (long long j = i * i; j <= n; j += i) {
					if (!factor_m[j]) factor_m[j] = i;
				}
			}
		}
	}
	bool is_prime(int x) const {
		return factor_m[x] == x;
	}
	std::vector<int> primes() const {
		return primes_m;
	}
	std::vector<int> primes(int x) const {
		std::vector<int> result;
		for (std::size_t i = 0; i < primes_m.size(); ++i) {
			if (primes_m[i] > x) break;
			result.push_back(primes_m[i]);
		}
		return result;
	}
	std::vector<std::pair<int, int>> prime_factor(int x) const {
		assert(1 <= x);
		std::vector<std::pair<int, int>> result;
		while (x != 1) {
			if (result.empty() || result.back().first != factor_m[x]) {
				result.emplace_back(factor_m[x], 1);
			} else {
				result.back().second++;
			}
			x /= factor_m[x];
		}
		return result;
	}
	std::map<int, int> prime_factor_map(int x) const {
		assert(1 <= x);
		std::map<int, int> result;
		while (x != 1) {
			result[factor_m[x]]++;
			x /= factor_m[x];
		}
		return result;
	}
	std::vector<int> prime_factor_vec(int x) const {
		assert(1 <= x);
		std::vector<int> result;
		while (x != 1) {
			result.push_back(factor_m[x]);
			x /= factor_m[x];
		}
		return result;
	}
	int divisors_count(int x) const {
		assert(1 <= x);
		int result = 1;
		for (auto [elem, cnt] : prime_factor(x)) {
			result *= cnt + 1;
		}
		return result;
	}
};
#line 3 "test/Sieve.test.cpp"
#include <iostream>
#include <algorithm>
#line 6 "test/Sieve.test.cpp"
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	Sieve sieve(100000000);
	const auto& primes = sieve.primes();
	int n;
	cin >> n;
	int ans = 0;
	while (n--) {
		int x;
		cin >> x;
		ans += sieve.is_prime(x);
		assert(sieve.is_prime(x) == binary_search(primes.begin(), primes.end(), x));
	}
	cout << ans << '\n';
}

Back to top page