Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
segmented sieve
//g++ 5.4.0 #include <bits/stdc++.h> using namespace std; typedef long long ll; void simpleSieve(int limit, vector<int>& primes){ bool mark[limit+1]; memset(mark,true,sizeof(mark)); for(int i=2;i*i<=limit;i++){ if(mark[i]==true){ for(int j=2*i;j<=limit;j+=i){ mark[j] = false; } } } for(int i=2;i<=limit;i++){ if(mark[i]==true){ cout<<i<<" "; primes.push_back(i); } } } void segmentedSieve(ll n){ int limit = sqrt(n); vector<int> primes; simpleSieve(limit,primes); int low = limit + 1; int high = 2*limit; while(low<=n){ if(high>n) high = n; bool mark[limit]; memset(mark,true,sizeof(mark)); for(int i=0;i<primes.size();i++){ int base = ((low/primes[i])*primes[i]); if(base<low) base = base + primes[i]; for(int j=base;j<=high;j+=primes[i]){ mark[j-low]=false; } } for(int i=0;i<limit;i++){ if(mark[i]==true) cout<<(i+low)<<" "; } low+=limit; high+=limit; } } int main() { segmentedSieve(1000000000); }
run
|
edit
|
history
|
help
0
poprawione_i_podzielone_1
passing by reference vs passing by value
Bind Function
point to a rvalue
TraiectorieIdeala
Matrix multiplication naive approach
PrePostIncrOp
Изволов#2
Compatibilità
test