I want to find the greatest prime number that is smaller than $x$, where $ x \in N$. I wonder that is there any formula or algorithm to find a prime ?
Asked
Active
Viewed 6,826 times
2 Answers
1
As Emilio Novati stated in a comment, the sieve of Eratosthenes will work. The sieve will probably be fast enough for your needs, although potentially faster approaches exist (see Lykos's answer).
I didn't want to bother converting it to pseudocode, so here is a function written in C that returns the greatest prime less than or equal to $N$.
#include <stdlib.h>
unsigned long primeNoGreaterThan(unsigned long N) {
unsigned long i,j,winner;
_Bool* primes = (_Bool*) malloc(N*sizeof(_Bool));
primes[0] = primes[1] = 0;
for(i = 2; i <= N; ++i)
primes[i] = 1;
for(i = 2; i <= N; ++i) {
if(primes[i]) {
winner = i;
for(j = i+i; j <= N; j += i)
primes[j] = 0;
}
}
free(primes);
return winner;
}
Mike Pierce
- 18,938
-
-
I think it would be easier and faster to test numbers smaller than x by trial division. for (size_t i=x-1; i>=2; --i){ for (size_t j=2; j*j<=i; ++j){ if (i%j==0) continue; } return i; } return 1; // where 1 is not really a prime... Although I have not done a runtime analysis. – Wolfgang Brehm May 26 '15 at 10:13
-
Code needs a small correctness edit, but even that naive trial division is much faster than sieving all numbers up to N every time. Set N to 10,000,000,000. Run prevprime 1000 times. Even a very fast sieve will take 2+ seconds per call. Doing the trivial trial division is 1000x faster. Using fast primality tests (e.g. Pari or Perl/ntheory) is over 100x faster yet. – DanaJ May 27 '15 at 00:50
-
@DanaJ, yeah I agree that trial division would be faster. I just had the sieve code handy. :) What is the correctness edit you are talking about, though? – Mike Pierce May 27 '15 at 01:27
-
@mapierce271, Sorry that wasn't clear -- Lykos's trial division needs a small edit (the continue is applying to the inner loop, which makes the result incorrect). The sieve looks fine though it does what the function name says (largest prime <= N) rather than the OP question (largest prime < N). It could be optimized, but that's a truly never-ending task that can be left to the reader. – DanaJ May 27 '15 at 01:36
-
You have
malloc(N*sizeof(_Bool))but you index intoprimes[N]in several places. – Praetorian Apr 13 '17 at 07:54 -
I haven't thought about C for awhile now. If you see how to fix it, please do go ahead and edit the code. – Mike Pierce Apr 13 '17 at 15:25
0
There are a few algorithms available. You could for example test for any number smaller than x, starting with x-1 if it is prime, that way if you use the AKS primality test you would probably get the best scaling algorithm for the problem you are describing (polynomial in log(x) ). You could also do simple trial division to assess primality for smaller numbers ($x<10^{10}$).
Wolfgang Brehm
- 753
-
1It is polynomial in $\log n$ if and only if the length of prime gaps is bounded from above by such a polynomial. That seems to be an open question (though there is numerical evidence that prime gaps are at most $O(\log^2n)$ long). – hmakholm left over Monica May 25 '15 at 22:27
-
Re AKS, when people ask about multiplication, do you suggest they implement Fürer's algorithm? – DanaJ May 25 '15 at 23:25
-
1@DanaJ In addition to OP's presumably-practical question, there's also an interesting theoretical question here, and this answer takes a step in that direction. AFAIK it's not actually known that one can find the largest prime less than $x$ in time polynomial in the number of bits of $x$; the result holds with some reasonable assumptions (e.g. Cramér's conjecture), but that fact itself still needs the existence of a polynomial-time primality test like AKS. – Steven Stadnicki May 25 '15 at 23:40
-
@StevenStadnicki, good point. There are a few directions an answer could take -- (1) fine for small inputs and programming problems (SoE), (2) fast in-practice solutions (e.g. what does Pari do), and (3) asymptotic complexity. The OP seems to like the sieve solutions. – DanaJ May 25 '15 at 23:50
-
@DanaJ As always this is a tradeoff between best scaling and the constant overhead. And it might well be that the scaling of the AKS will not be changed by introducing a better scaling multiplication method, as it could be hidden behind steps that have a worse scaling. It is becoming interesting and complicated... – Wolfgang Brehm May 26 '15 at 10:17
-
@StevenStadnicki Jes OP does but I cannot understand why. The sieve is great for finding all primes less than x but I think simple trial division will still be faster, although the scaling could be very similar. – Wolfgang Brehm May 26 '15 at 10:24
-
If the input was, for example, $10^{19}$, then sieving for all primes below x would be terribly wasteful, and trial division tests would also be really slow. Or $10^{1900}$. You should use a fast probable prime test (easily deterministic below $2^{64}$), skipping obvious composites using a wheel or partial sieve (e.g. to 30 merits). Then you run a single proof on the final answer if desired -- no need to bother with a proof on all the intermediates that BPSW would get take care of much faster. – DanaJ May 26 '15 at 18:17
-
1@DanaJ you are right this is probably the best scaling method.
But for small numbers I cannot see the advantage of the sieve over trial division.
– Wolfgang Brehm May 26 '15 at 19:04 -
@Lykos, I believe you are right. If one were doing many calls with small inputs, a cached sieve result can be good. But sieving every call? Clearly not a good solution as N gets larger. Take the perfectly reasonable input $N=10^{12}$. It's fine with trial division at ~9 milliseconds per call. Sieving is unreasonable slow -- even primesieve takes 6 minutes single threaded (the sieve in the answer uses >32GB so doesn't work at all). Pari takes 6 microseconds, Perl/ntheory takes about 1.5 microseconds. – DanaJ May 27 '15 at 01:25
precprime(n-1)in Pari/GP,prev_prime(n)in Perl/ntheory and FLINT,NextPrime[n,-1]in Mathematica,prevprime(n)in Maple and Python/SymPy,previous_prime(n)in SAGE,PreviousPrime(n)in MAGMA. Some of these are open source. The trivial solution is go backwards by one until a fast primality test returns true or the input was 2. One can optimize in many ways. – DanaJ May 25 '15 at 23:33