結果
問題 | No.713 素数の和 |
ユーザー |
![]() |
提出日時 | 2020-07-25 23:02:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,562 bytes |
コンパイル時間 | 2,100 ms |
コンパイル使用メモリ | 196,708 KB |
最終ジャッジ日時 | 2025-01-12 05:40:01 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 |
ソースコード
#include <bits/stdc++.h>using namespace std;class Prime {public:template <typename T>static bool is_prime(T n) {if (n == 0 || n == 1) return false;if (n == 2) return true;if (n % 2 == 0) return false;for (T i = 3; i * i < n + 1; i += 2) {if (n % i == 0) return false;}return true;}template <typename T>static std::vector<T> factor(T n) {std::vector<T> res;for (T i = 2; i * i < n + 1; i++) {while (n % i == 0) {n /= i;res.emplace_back(i);}}if (n != 1) res.emplace_back(n);return res;}template <typename T>static T totient(T n) {T res = 1;std::vector<T> primes = factor(n);std::map<T, int> mp;for (T p : primes) {mp[p]++;}for (const auto &[p, c] : mp) {res *= pow(p, c - 1) * (p - 1);}return res;}template <typename T>static std::vector<T> sieve_of_eratosthenes(T n) {std::vector<bool> is_prime(n + 1, true);is_prime[0] = is_prime[1] = false;for (T i = 2; i * i < n + 1; i++) {if (!is_prime[i]) continue;for (T k = 2 * i; k < n + 1; k += i) {is_prime[k] = false;}}std::vector<T> res;for (T i = 0; i < n + 1; i++) {if (is_prime[i]) res.emplace_back(i);}return res;}};int main() {ios::sync_with_stdio(false);cin.tie(0);int N;cin >> N;auto primes = Prime::sieve_of_eratosthenes(N);int res = 0;for (auto p : primes) {res += p;}cout << res << '\n';return 0;}