2
$\begingroup$

This came up as a part of algorithm puzzles:
Given a number $N$, how to find the prime $P$ such that $P<N$ and the difference $N-P$ is minimum.
For small $N$, simple sieves do work, but I'm unable to find solution for large values of $N$.
I tried to modify the sieves to somehow look over large values only, didn't get anywhere.
Any solutions/hints for this?

$\endgroup$
  • 1
    $\begingroup$ Off the top of my head: Let $m$ the product of some initial segment of primes (how many would depend on the size of $N$). For example, $m=2\cdot3\cdot5\cdot7\cdot11\cdot13=30030$. Make an list of all the numbers below $m$ with $\gcd(m,x)=1$. This list can be quickly used to pick non-multiples of the prime factors of $m$ in any segment of numbers. Now start at $N-1$ and move downwards, checking the candidates in turn. $\endgroup$ – Harald Hanche-Olsen May 3 '13 at 17:08
  • $\begingroup$ When you have a candidate, if $N$ is very large use a probabilistic primality test such as Miller–Rabin first, then follow up with a proper proof of primality if that is required. $\endgroup$ – Harald Hanche-Olsen May 3 '13 at 17:10
  • $\begingroup$ This counting down can be painful. If candidates can be enumerated fast, that'll be nice $\endgroup$ – Avogadro May 3 '13 at 17:32
  • $\begingroup$ Enumerating candidates fast is what the first part was all about. $\endgroup$ – Harald Hanche-Olsen May 3 '13 at 18:12
  • $\begingroup$ what for large N (say $10^{16}$), there the reduced complexity in search space still seems impractical $\endgroup$ – Avogadro May 3 '13 at 18:47
1
$\begingroup$

Start counting downward from $N-1$ After trial division by some small primes, you can use one of a number of probabilistic tests like the Fermat primality test. If $p$ is prime, $a^{p-1} \equiv 1 \pmod p$. This can be checked quickly. If it is true for a few $a$, the chance of $p$ being composite is very small. If you insist on certainty, you can finish up with one of the deterministic tests.

$\endgroup$
  • $\begingroup$ This counting down can be painful. If candidates can be enumerated fast, that'll be nice $\endgroup$ – Avogadro May 3 '13 at 17:28
  • $\begingroup$ @Avogadro: The trial division can help a lot. Even $2,3,5$ eliminate all but 8 out of 30. You can make a list of the moduli that are acceptable and avoid the trial divisions. $\endgroup$ – Ross Millikan May 3 '13 at 18:07
  • $\begingroup$ what for large N (say $10^{16}$), there the reduced complexity in search space still seems impractical. (sorry for copy-pasting comments from top again :) ) $\endgroup$ – Avogadro May 3 '13 at 18:48
  • 2
    $\begingroup$ @Avogadro: around $10^{16}$ about one in $37$ numbers is prime, so if you use the $\pmod {30}$ restriction, you should only have to try $10$ on the average. I don't think that is bad. $\endgroup$ – Ross Millikan May 3 '13 at 19:13
  • $\begingroup$ As an aside, if you're used to using primes for public-key cryptography then primes around $10^{16}$ are pitifully small. $\endgroup$ – Harald Hanche-Olsen May 3 '13 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.