prime generation

[udvat]

I have to find out the primes within the range 100000000. but i dont have the option of having a large array(so i cant use seive). wud anybody plz give me the solution?the code should be faster.

[UFP2161]

You can still declare an array big enough to sieve that. Just pack the booleans in bits instead of bytes.

100,000,000 / 8 bits per byte = 12.5 million bytes (which is less than the 32MB limit)

[rjhadley]

You could also try a primality test such as the Rabin-Miller Algorithm. (It's basically a probablistic test along the lines of Fermat's Little Theorem, although there are also deterministic versions).

[Caesum]

personally i would code a couple of strong psp tests for the first few primes, and there are well known exceptions to them which you can incorporate in your algorithm if necessary.

[udvat]

thankx to u all. am sending my code here. the judge says my code takes a long time to compile and it may because of using more than 16 mb of memory.its a problem from usaco training gateway.name is"prime palindrom"

************code has been removed

[LPH]

thankx to u all. am sending my code here. the judge says my code takes a long time to compile and it may because of using more than 16 mb of memory.its a problem from usaco training gateway.name is"prime palindrom"

u can try this:
only generate the prime under 10000 (since the square root of 100000000 (i hope i didn't mislook; there are 8 zeros) is 10000), then when u try to determine whether a number is a prime or not, try to divide it with all the primes from 2 to the square root of the number (that's why we only generate the prime under 10000, 'cause we have enough prime to determine number up to 100000000). if none of them can exactly divide your number, it's a prime; otherwise, it's not a prime.

according to my experience, there are about 12000 primes under 10000(if my memory is right ).

hope this'll be helpful

[junjieliang]

Some hints for you:

1. Instead of checking whether a number is prime and then whether it's a palindrome, consider doing it the other way.

2. There are very few prime palindromes around. According to my code there's less than 10000 of them only *hint hint*.

Good luck!

[Caesum]

and obviously there is only one prime palindrome with an even number of digits.....

[udvat]

special thankx to Caesum ,LPH & UFP2161 .following ur suggesstions atlast i got AC.i cant get the hints provided by junjieliang. wud u plz make it easier for me?thanks to all again

[junjieliang]

Now that I read through my post again I guess I wasn't too clear before. Actually I meant that you generate the palindromes and then check whether they are primes. This will be faster than check every number. Then you can store these palindrome primes into an array and check against the range in the input.

[udvat]

yes, its a good idea. i will try it. thank u very much