test/primeSieve.test.cpp

View this file on GitHub
Last update: 2023-03-05 22:25:53+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_C

Depends on

primeSieve (エラトステネスの篩） (src/math/primeSieve.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_C"

#include "../src/math/primeSieve.hpp"

#include <iostream>

int main() {
	zawa::primeSieve siv(100000000);
	int n; std::cin >> n;
	int ans = 0;
	for (int _ = 0 ; _ < n ; _++) {
		int v; std::cin >> v;
		ans += siv[v];
	}
	std::cout << ans << std::endl;
}

#line 1 "test/primeSieve.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_C"

#line 2 "src/math/primeSieve.hpp"

#include <vector>

namespace zawa {

class primeSieve {
private:
	std::vector<bool> sieve;

public:
	primeSieve() {}
	primeSieve(std::size_t n) : sieve(n + 1, true) {
		if (n >= 0) {
			sieve[0] = false;
		}
		if (n >= 1) {
			sieve[1] = false;
		}
		for (std::size_t i = 2 ; i <= n ; i++) {
			if (sieve[i]) {
				for (std::size_t j = i * 2 ; j <= n ; j += i) {
					sieve[j] = false;
				}
			}
		}
	}

	inline bool operator[](std::size_t i) const {
		return sieve[i];
	}

	inline std::size_t size() const {
		return sieve.size();
	}
};

}// namespace zawa
#line 4 "test/primeSieve.test.cpp"

#include <iostream>

int main() {
	zawa::primeSieve siv(100000000);
	int n; std::cin >> n;
	int ans = 0;
	for (int _ = 0 ; _ < n ; _++) {
		int v; std::cin >> v;
		ans += siv[v];
	}
	std::cout << ans << std::endl;
}