Prime number less than or equal to N

  • Thread starter Avichal
  • Start date
  • Tags
    Prime
In summary, for finding the largest prime number less than or equal to a given number N<=1018, the brute-force method of iterating from N in decreasing order and checking for primality by iterating until the square-root of the number can be used, but this method takes a long time for large numbers. Alternatively, using a primality test such as the Miller-Rabin pseudo-primality test can greatly reduce the time needed to find the largest prime number. Other options include using Mathematica's PrimeQ function or the 'maxima' software, which is free and has a 'primep' function. Overall, it is important to research and explore different methods before resorting to a brute-force approach.
  • #1
Avichal
295
0

Homework Statement


Given a number N<=1018, 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 Nmax = 1018 which will take too much time.
Any ideas?
 
Physics news on Phys.org
  • #2
Avichal said:

Homework Statement


Given a number N<=1018, 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 Nmax = 1018 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.
 
  • #3
jackmell said:
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.
 
  • #4
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. :-)
 
  • #5
The Electrician said:
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.
 
Last edited:
  • #6
Dick said:
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 1018.
Thanks a lot!
 

1. What is a prime number?

A prime number is a positive integer that is only divisible by 1 and itself. In other words, it has no other factors besides 1 and itself.

2. How do I find all the prime numbers less than or equal to N?

To find all the prime numbers less than or equal to N, you can use a method called the "Sieve of Eratosthenes." This method involves creating a list of numbers from 2 to N and systematically crossing out all the multiples of each prime number until you are left with a list of only prime numbers.

3. What is the largest prime number less than or equal to N?

The largest prime number less than or equal to N will vary depending on the value of N. As N increases, so does the likelihood of finding larger prime numbers. As of 2021, the largest known prime number is 2^82,589,933 - 1, which has over 24 million digits.

4. Are there any patterns or rules for prime numbers less than or equal to N?

While there are some patterns and rules that can help identify prime numbers, such as the fact that all prime numbers (except 2) are odd, there is no general formula or rule that can generate all prime numbers less than or equal to N. Prime numbers are considered to be random and unpredictable.

5. Why are prime numbers important in mathematics?

Prime numbers play a crucial role in many areas of mathematics, including number theory, cryptography, and computer science. They are also used in real-life applications, such as in creating secure encryption codes and in determining the most efficient way to distribute resources. Additionally, prime numbers have been studied and admired by mathematicians for centuries due to their unique properties and mysterious nature.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Programming and Computer Science
Replies
22
Views
630
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
19
Views
4K
  • Calculus and Beyond Homework Help
Replies
10
Views
2K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
Back
Top