Prime generator

#1

I am getting TLE even after applying Segmented Sieve.
plz help.
My Code is https://ide.codingblocks.com/s/197828

#2

Please share the question link

#3

Meanwhile you can see this https://ide.codingblocks.com/s/197867. This is the solution to https://hack.codingblocks.com/app/contests/953/388/problem and uses segmented sieve that you are trying to use.

#4

question link https://www.spoj.com/problems/PRIME1/
Your Solution gets accepted
Can u plz tell how time is reduced as compared to my code?

#5

Try calling the sieve function only once before any test case, that should reduce time complexity.

Precompute all primes upto max size. Refer to the code I sent , it should make it clear.

#6

I called sieve function outside all test case but still getting TLE.
I went through code but didn’t get how to reduce time plz tell the logic

#7

The updates are key here.
if(a>i){
if(a%i) j=a-a%i+i;
//starting point should be correct

		else j=a;
		}	
        else j=i;
        for(;j<=b;j+=i){

// I am incrementing by i but in your case you are doing by just 1 , so your time complexity
O(Range of primes* (b-a)) which is large.

            if(j!=i) pp[j-a]=0;
        }

Why incrementing by i works is because once I find a multiple, next multiple can only occur after i.
So it reduces to sieve like complexity.

#8

I understood and did same but it is showing runtime error plz help
code link is https://ide.codingblocks.com/s/199436

#9

Increase the size of your prime array as you are calling sieve for a large number

#10

I am calling sieve for 1000000000 and sqrt of 1000000000 is 31622.7766017 so I chose 31624 Is this wrong?

#11

You had copied the updates incorrectly, here https://ide.codingblocks.com/s/199969 please see, now its working.

#12

ya mine also gets accepted.Thanks

1 Like