test/EnumeratePrimes.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/EnumeratePrimes.cpp
• math/Eratosthenes.cpp

Code

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

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

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

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

std::vector<bool> Eratosthenes(size_t n) {
	std::vector<bool> result(n + 1, true);
	result[0] = result[1] = false;
	for (size_t i = 2; i * i <= n; ++i) {
		if (result[i]) {
			for (size_t j = i * i; j <= n; j += i) result[j] = false;
		}
	}
	return result;
}
#line 4 "math/EnumeratePrimes.cpp"

std::vector<int> EnumeratePrimes(std::size_t n) {
	std::vector<int> result;
	auto p = Eratosthenes(n);
	for (std::size_t i = 2; i <= n; ++i) {
		if (p[i]) result.push_back(i);
	}
	return result;
}
#line 3 "test/EnumeratePrimes.test.cpp"
#include <iostream>
#include <algorithm>
using namespace std;

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

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

Back to top page