in the question prime number generator of medium level i have used sieve of erasthones and i am getting a run time of 0.6 sec on ideone for the limits test case:10
2 20
3 5
100 1000
100 10000
1234 12345
999990000 1000000000
1 10000
400 40000
23 23000
1 1000
but its still showing me time limit exceeded my code submission is 1349391…pls help
use sieve of atkin…it will be faster
Sieve of Atkin solves you will be more efficient then erasthones.
Sieve of Atkin algorithm:
All remainders are modulo-sixty remainders (divide the number by sixty and return the remainder).
All numbers, including x and y, are positive integers.
Flipping an entry in the sieve list means to change the marking (prime or nonprime) to the opposite marking.
Create a results list, filled with 2, 3, and 5.
Create a sieve list with an entry for each positive integer; all entries of this list should initially be marked nonprime.
For each entry number n in the sieve list, with modulo-sixty remainder r :
If r is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to 4x2 + y2 = n.
If r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x2 + y2 = n.
If r is 11, 23, 47, or 59, flip the entry for each possible solution to 3x2 ? y2 = n when x > y.
If r is something else, ignore it completely.
Start with the lowest number in the sieve list.
Take the next number in the sieve list still marked prime.
Include the number in the results list.
Square the number and mark all multiples of that square as nonprime.
Repeat steps five through eight.
This results in numbers with an odd number of solutions to the corresponding equation being prime, and an even number being nonprime.
Well it is not a big Deal…Try to solve without using mod(%)…
you can also use segmented sieve of erasthones…for n>1000000…i think this will help…
thanks a lot