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
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<bool>(lim)tobitset<lim>. 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: wiki
About O(n): code
About 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 => precalculation
Let N > n > N2 / 3 => n = N / x, where x ≤ N1 / 3 and d ≤ N1 / 3. There are only O(N2 / 3) such pairs <x, d>. So there are only O(N2 / 3) non-trivial states.
Last case: N = n. There are
such states.
Both
vector<bool>andbitsetare slow, if memory is not a constraint, it is better to usevector<char>.yes. i am considering this specific change too !!
There is an easy coding O(n) algorithm. I don't know how it is called in English, so here the code comes.
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)