Блог пользователя Flawless

Автор Flawless, 11 лет назад, По-английски

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
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      About n2 / 3: wiki

      About O(n): code

      About O(): code

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              11 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 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)?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
11 лет назад, # |
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)