1

I want to calculate prime number just below a number. How can this be done efficiently.

I used Sieve of Eratosthenes but it failed as my numbers are in range 10^20

Any other algorithm??

Mayank Jain
  • 2,504
  • 9
  • 33
  • 52
  • 2
    Count down from your number, throw a http://en.wikipedia.org/wiki/Fermat_primality_test at each number you meet, the first one to withstand the test ought to give you a good candidate too take a closer look at. – flup May 05 '13 at 17:53

2 Answers2

7

The chance of a random 20-digit number being prime is approximately 1/20 (source). If you want the largest prime below x, start at x-1 and run a primality test on each number, working your way down until you find a prime. The following is a related answer I gave and lists a highly reliable and extremely fast pseudoprime test that should suffice:

how to test a prime number 1000 digits long?

Community
  • 1
  • 1
Sam Harwell
  • 97,721
  • 20
  • 209
  • 280
  • 1
    The chance is approximately `1/(20*log 10)` which is roughly `1/46`. (And before going for the big guns, trial division by small primes to cheaply weed out most composites is advisable.) – Daniel Fischer May 05 '13 at 18:06
  • A simple `GCD(x, 30030)` covers the trial division by small primes (30030 = 2*3*5*7*11*13). – Sam Harwell May 05 '13 at 19:19
  • Isn't GCD quite a few times more expensive than division? I'd recommend skipping even numbers (divisible by 2), skipping numbers ending in 5 (divisible by 5) and possibly only then doing `GCD(x, 3*7*11*13)` (or similar). Note that having the sequence of decrements incorporate skipping all and only numbers divisible by 2, 3, 5 and even 7 and possibly more numbers shouldn't be too difficult. – Bernhard Barker May 05 '13 at 21:09
0

Use a segment of a sieve for sufficiently many numbers just below n so that you can be reasonable sure it contains a prime (say a couple of thousand numbers). Then sieve with small primes to remove most of the non-primes. Use a full primality test on the remaining numbers (either probabilistic, or for 20 digits trial division up to the root might still be reasonable).

How many small primes you use for sieving depends on the relative cost of sieving versus running the full primality test.

starblue
  • 55,348
  • 14
  • 97
  • 151