Run Code
|
API
|
Code Wall
|
Users
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Segmented Sieve
//Segmented Sieve : generate prime no. less than N #include<bits/stdc++.h> using namespace std; typedef long long ll; vector<ll> simpleSieve(ll limit, vector<ll> prime){ bool isPrime[limit+1]; memset(isPrime, true, sizeof(isPrime)); for(int i=2;i*i<limit;++i){ if(isPrime[i]){ for(int j=i*i;j<limit;j+=i){ isPrime[j] = false; } } } for(ll i=2;i<limit;++i){ if(isPrime[i]){ cout<<i<<" "; prime.push_back(i); } } return prime; } void segmentedSieve(ll n){ ll limit = sqrt(n)+1; vector<ll> prime; prime = simpleSieve(limit,prime); ll low = limit; ll high = 2*limit; while(low<=n){ if(high>=n){ high = n; } bool isPrime[limit+1]; memset(isPrime, true, sizeof(isPrime)); for(ll i = 0;i<prime.size();i++){ ll curPrime = prime[i]; ll base = (low/curPrime) * curPrime; if(base<low){ base+=curPrime; } for(ll j=base;j<high;j+=curPrime){ isPrime[j-low] = false; } if(base==curPrime) isPrime[base-low] = true; } for(ll i=low;i<high;i++){ if(isPrime[i-low]){ cout<<i<<" "; } } low+=limit; high+=limit; } } int main(){ ll n = 100; segmentedSieve(100); return 0; }
run
|
edit
|
history
|
help
0
Please
log in
to post a comment.
frndclass
HelloWorld
test
1028D
compile-time check of existness of method of a class
Scope guarding
pointer to template function
copy_if c++98
Float
printAllPathsInMatrix
Please log in to post a comment.