Flawless's blog

Help required in Improving Prime Sieve
By Flawless, 12 years ago, In English

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

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I know two ways to improve this:

  1. Your implementation have small constant, but still work in O(nloglogn). It's possible to do it in O(n).

  2. 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) to bitset<lim>. And if problem is "find number of primes from 1 to n", it's solvable in O(n2 / 3)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you enlightened me for the way to do so ??

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      About n2 / 3: wiki

      About O(n): code

      About O(): code

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the link!! memory management was wonderful , thanks again !!

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        in sqrt(n) code, you can initialize pos with i * i. sqrt(n) memory is very good optimization because of processor's cache.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          you mean regarding that 3MB cache L2 . ?? . i never know it affects that. thanks for giving this info :)

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            On my old machine the optimal value for step was 1 << 18, not sqrt(10^9).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              no i meant on when you said "sqrt(n) memory is very good optimization because of processor's cache." ??

              → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Φ(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.

          → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Both vector<bool> and bitset are slow, if memory is not a constraint, it is better to use vector<char>.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes. i am considering this specific change too !!

      → Reply
»
12 years ago, # |
← Rev. 7   Vote: I like it +1 Vote: I do not like it

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)

→ Reply