### 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[1]=isprime[0]=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;
}
}


Can i improve this more ??? Please help

• +10

 » 9 years ago, # | ← Rev. 2 →   +8 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)
•  » » 9 years ago, # ^ |   0 can you enlightened me for the way to do so ??
•  » » » 9 years ago, # ^ |   +3 About n2 / 3: wikiAbout O(n): codeAbout O(): code
•  » » » » 9 years ago, # ^ |   0 Thanks for the link!! memory management was wonderful , thanks again !!
•  » » » » 9 years ago, # ^ |   0 in sqrt(n) code, you can initialize pos with i * i. sqrt(n) memory is very good optimization because of processor's cache.
•  » » » » » 9 years ago, # ^ |   0 you mean regarding that 3MB cache L2 . ?? . i never know it affects that. thanks for giving this info :)
•  » » » » » » 9 years ago, # ^ |   0 On my old machine the optimal value for step was 1 << 18, not sqrt(10^9).
•  » » » » » » » 9 years ago, # ^ |   0 no i meant on when you said "sqrt(n) memory is very good optimization because of processor's cache." ??
•  » » » » 9 years ago, # ^ |   0 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)?
•  » » » » » 9 years ago, # ^ |   +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.
•  » » 9 years ago, # ^ |   +1 Both vector and bitset are slow, if memory is not a constraint, it is better to use vector.
•  » » » 9 years ago, # ^ |   0 yes. i am considering this specific change too !!
 » 9 years ago, # | ← Rev. 7 →   +1 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[0]=isp[1]=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)