結果
問題 | No.8079 アルベド |
ユーザー |
![]() |
提出日時 | 2021-04-01 23:25:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 158 ms / 2,000 ms |
コード長 | 1,780 bytes |
コンパイル時間 | 1,896 ms |
コンパイル使用メモリ | 144,780 KB |
最終ジャッジ日時 | 2025-01-20 07:23:13 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#define _USE_MATH_DEFIMES #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cctype> #include <climits> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <limits> #include <list> #include <map> #include <numeric> #include <queue> #include <random> #include <regex> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> const int MOD = 1'000'000'007; const int MOD2 = 998'244'353; const int INF = 1'000'000'000; //1e9 const int NIL = -1; const long long LINF = 1'000'000'000'000'000'000; // 1e18 const long double EPS = 1E-10; template<class T, class S> inline bool chmax(T &a, const S &b){ if(a < b){ a = b; return true; } return false; } template<class T, class S> inline bool chmin(T &a, const S &b){ if(b < a){ a = b; return true; } return false; } std::vector<bool> isPrime; void Eratosthenes(int n){ if(n + 1 <= int(isPrime.size())) return; isPrime.resize(n+1, true); isPrime[0] = isPrime[1] = false; for(int i = 2; i * i <= n; ++i){ if(isPrime[i]){ for(int j = i; i * j <= n; ++j) isPrime[i*j] = false; } } } int main(){ Eratosthenes(100000); std::vector<int> cnt(100001, 0); for(int i{1}; i <= 100000; ++i){ cnt[i] = cnt[i-1]; if(isPrime[i]) ++cnt[i]; } int T; std::cin >> T; while(T--){ int N; std::cin >> N; std::cout << cnt[N] << "\n"; } return 0; }