1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prime number less than or equal to N

  1. May 3, 2013 #1
    1. The problem statement, all variables and given/known data
    Given a number N<=1018, I need to find the largest prime number less than or equal to N

    2. Relevant equations

    3. 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 Nmax = 1018 which will take too much time.
    Any ideas?
  2. jcsd
  3. May 3, 2013 #2
    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.
  4. May 3, 2013 #3


    User Avatar
    Science Advisor
    Homework Helper

    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.
  5. May 3, 2013 #4

    The Electrician

    User Avatar
    Gold Member

    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. :-)
  6. May 3, 2013 #5


    User Avatar
    Science Advisor
    Homework Helper

    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.
    Last edited: May 3, 2013
  7. May 4, 2013 #6
    Miller-Rabin pseudo-primality test works like a charm. Its very fast for numbers as high as 1018.
    Thanks a lot!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted