### Flawless's blog

By Flawless, 9 years ago, I know you can get an AC in problem with normally optimized prime sieve. but sometimes while doing problem on SPOJ. i noticed when i have execution time of 2 sec (for example), many good coders (Respected) have brought down their execution time to 0.5 sec around .

Here is what i have done for my optimized prime sieve.

Optimization i have done-
1. running main iteration loop to only square root of Limit.
2. avoid for even numbers.
3. not checking for multiple of 2 and 3
4. Prime numbers are of form 6k+1 or 6k+5.
5. in inner loop of j, insted of j+=i, i did j+=2*i. because i*i(as i will be odd for sure, i haven't run this loop for "2") will be odd for sure. so i*i+i will be odd for sure. so skip it by j+=2*i


Since even numbers and multiple of 3 are never marked. so they will never be checked while collecting all primes

 #define lim 10000009
vector<bool> isprime(lim,1);
void sieve()
{
int i,j,t,v,sq;
isprime=isprime=0;
sq=sqrt(lim);
for(i=5,t=2;i<=sq; )
{
if(isprime[i])
{
for(j=i*i;j<lim;j+=2*i)
isprime[j]=0; // 0 means composite- not prime , 1 means prime
}
i+=t;
t=6-t;
}
}  Comments (13)
 » 9 years ago, # | ← Rev. 2 →   I know two ways to improve this: Your implementation have small constant, but still work in O(nloglogn). It's possible to do it in O(n). Your implementation uses O(n) of memory. It's possible to use only O( ) of memory. UPD: Also you may try to change vector(lim) to bitset. And if problem is "find number of primes from 1 to n", it's solvable in O(n2 / 3)
•  » » can you enlightened me for the way to do so ??
•  » » » About n2 / 3: wikiAbout O(n): codeAbout O( ): code
•  » » » » Thanks for the link!! memory management was wonderful , thanks again !!
•  » » » » in sqrt(n) code, you can initialize pos with i * i. sqrt(n) memory is very good optimization because of processor's cache.
•  » » » » » you mean regarding that 3MB cache L2 . ?? . i never know it affects that. thanks for giving this info :)
•  » » » » » » On my old machine the optimal value for step was 1 << 18, not sqrt(10^9).
•  » » » » » » » no i meant on when you said "sqrt(n) memory is very good optimization because of processor's cache." ??
•  » » » » Thanks for method with O(n2 / 3). What is proof that count of subsets of different primes (less or equal ) with their product small or equal n is O(n2 / 3)?
•  » » » » » Φ(N, d) — amount of numbers from 1 to N with all prime divisors greater than d.π(N) = Φ(N, ) + π( )Φ(n, d) = Φ(n, d  -  1) — Φ(n / d, d)Let n  ≤  N2 / 3 => precalculationLet N > n > N2 / 3 => n = N / x, where x  ≤  N1 / 3 and d  ≤  N1 / 3. There are only O(N2 / 3) such pairs . So there are only O(N2 / 3) non-trivial states.Last case: N = n. There are such states.
•  » » Both vector and bitset are slow, if memory is not a constraint, it is better to use vector.
•  » » » yes. i am considering this specific change too !!
 » 9 years ago, # | ← Rev. 7 →   There is an easy coding O(n) algorithm. I don't know how it is called in English, so here the code comes. const int MAXP=10000000; const int MAXPS=664579; bool isp[MAXP+1]; int pp[MAXP+1]; int fac[MAXP+1]; int ps; int p[MAXPS]; void make_prime_table() { memset(isp,true,sizeof(isp)); isp=isp=false; for(int i=2;i<=MAXP;i++) { if (isp[i]) pp[p[ps]=i]=ps,ps++,fac[i]=i; for (int j=0;p[j]*i<=MAXP;j++) { isp[p[j]*i]=false,fac[p[j]*i]=p[j]; if(i%p[j]==0) break; } } } isp[x] stands for whether x is a prime, fac[x] is the smallest prime factor of x. UPD[http://www.csie.ntnu.edu.tw//Prime.html#a2]a web page about this algorithm in Chinese, you can use google translate to understand it.(http://www.csie.ntnu.edu.tw/~u91029/Prime.html#a2)