Help required in Improving Prime Sieve

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

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

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; } } }

Комментарии (13)

Написать комментарий?

Burunduk1

13 лет назад, скрыть # |

← 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( $\text{[math]}$ ) 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(n^2 / 3)

→ Ответить

Flawless

13 лет назад, скрыть # ^ |

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

About n^2 / 3: wiki

About O(n): code

About O( $\text{[math]}$ ): code

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

goo.gl_SsAhv

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." ??

hydrastuff

Thanks for method with O(n^2 / 3). What is proof that count of subsets of different primes (less or equal $\text{[math]}$ ) with their product small or equal n is O(n^2 / 3)?

Φ(N, d) — amount of numbers from 1 to N with all prime divisors greater than d.

π(N) = Φ(N, $\text{[math]}$ ) + π( $\text{[math]}$ )

Φ(n, d) = Φ(n, d - 1) — Φ(n / d, d)

Let n ≤ N^2 / 3 => precalculation

Let N > n > N^2 / 3 => n = N / x, where x ≤ N^1 / 3 and d ≤ N^1 / 3. There are only O(N^2 / 3) such pairs <x, d>. So there are only O(N^2 / 3) non-trivial states.

Last case: N = n. There are $\text{[math]}$ such states.

andreyv

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

yes. i am considering this specific change too !!

boleyn.su

← 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.

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)

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