This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/enumerate_primes #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../math/enumerate_primes.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,a,b; cin>>n>>a>>b; auto ps=enumerate_primes(n); vector<int> qs; for(int i=b;i<(int)ps.size();i+=a) qs.emplace_back(ps[i]); cout<<ps.size()<<' '<<qs.size()<<endl; for(int i=0;i<(int)qs.size();i++){ if(i) cout<<' '; cout<<qs[i]; } cout<<endl; return 0; }
#line 1 "test/yosupo/enumerate_primes.test.cpp" // verification-helper: PROBLEM https://judge.yosupo.jp/problem/enumerate_primes #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "math/enumerate_primes.cpp" #line 3 "math/enumerate_primes.cpp" using namespace std; #endif //BEGIN CUT HERE // O(n) vector<int> enumerate_primes(int n){ vector<bool> dp((n+1)/2,false); vector<int> ps; ps.reserve(n/10); if(2<=n) ps.emplace_back(2); for(int i=3;i<=n;i+=2){ if(!dp[i/2]) ps.emplace_back(i); for(int j=1;i*ps[j]<=n;j++){ dp[i*ps[j]/2]=1; if(i%ps[j]==0) break; } } return ps; } //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 8 "test/yosupo/enumerate_primes.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,a,b; cin>>n>>a>>b; auto ps=enumerate_primes(n); vector<int> qs; for(int i=b;i<(int)ps.size();i+=a) qs.emplace_back(ps[i]); cout<<ps.size()<<' '<<qs.size()<<endl; for(int i=0;i<(int)qs.size();i++){ if(i) cout<<' '; cout<<qs[i]; } cout<<endl; return 0; }