Prime number less than or equal to N

[Avichal]

Homework Statement

Given a number N<=10¹⁸, I need to find the largest prime number less than or equal to N

Homework Equations

The Attempt at a Solution

I can only think of a brute-force solution i.e. iterate from N in decreasing order until you get a prime number.
And to check if number is prime just iterate till its square-root. If it has no factors then it is prime else its not.

But this won't work as N_max = 10¹⁸ which will take too much time.
Any ideas?

 

[jackmell]

Homework Statement

Given a number N<=10¹⁸, I need to find the largest prime number less than or equal to N

Homework Equations

The Attempt at a Solution

I can only think of a brute-force solution i.e. iterate from N in decreasing order until you get a prime number.
And to check if number is prime just iterate till its square-root. If it has no factors then it is prime else its not.

But this won't work as N_max = 10¹⁸ which will take too much time.
Any ideas?

You can start by googling about it. Like "prime number tests". Get one and then start counting backwards. That's one way. The lazy way is to use Mathematica's PrimeQ. Better in my opinion to first give it a few hours, maybe one then of just researching on the internet how to check a number for prime, maybe write some code to implement the process even if you do it only for much smaller numbers. Get some idea about what to do then if your efforts fail for 10^(18), find a machine running Mathematica and code it.

 

[Dick]

You can start by googling about it. Like "prime number tests". Get one and then start counting backwards. That's one way. The lazy way is to use Mathematica's PrimeQ. Better in my opinion to first give it a few hours, maybe one then of just researching on the internet how to check a number for prime, maybe write some code to implement the process even if you do it only for much smaller numbers. Get some idea about what to do then if your efforts fail for 10^(18), find a machine running Mathematica and code it.

I'd agree with that. Testing all of the numbers up to sqrt(n) is a pretty time intensive primality test, it will take hours. On the other hand the prime number theorem tells you that about one in every log(10^18)~41 numbers is prime in that neighborhood. So you don't have to test that many numbers. Mathematica is not your only other option if you want a canned primality test. Get a copy of 'maxima'. It's free! It has a 'primep' function. The first prime below 10^18 is 999999999999999989. Took a second or two once you've written the function to count backwards.

 

[The Electrician]

I would have thought Wolfram Alpha could do this, but it seems to choke on numbers as large as 1000000000000000000

But, Mathematica itself has a function NextPrime[10^18,-1] that finds the prime in question in 16 milliseconds. :-)

 

[Dick]

I would have thought Wolfram Alpha could do this, but it seems to choke on numbers as large as 1000000000000000000

But, Mathematica itself has a function NextPrime[10^18,-1] that finds the prime in question in 16 milliseconds. :-)

Ok, checking the actual timing maxima finds the prime in about 2ms and will factor a number of that size in about 400ms (worst case, where the number is actually prime). Reading the description of the algorithm it uses a Miller-Rabin pseudo-primality test for numbers over 10^16, so there is a vanishing small probability it might be wrong. Using 'factor' shows it's not. Oh, and I also wrote a naive version of the sqrt(n) test and applied it to that number a few hours ago. I'd tell you how long it took, but it's still running.

 

[Avichal]

Ok, checking the actual timing maxima finds the prime in about 2ms and will factor a number of that size in about 400ms (worst case, where the number is actually prime). Reading the description of the algorithm it uses a Miller-Rabin pseudo-primality test for numbers over 10^16, so there is a vanishing small probability it might be wrong. Using 'factor' shows it's not. Oh, and I also wrote a naive version of the sqrt(n) test and applied it to that number a few hours ago. I'd tell you how long it took, but it's still running.

Miller-Rabin pseudo-primality test works like a charm. Its very fast for numbers as high as 10¹⁸.
Thanks a lot!