Physics Van 3-site Navigational Menu

Physics Van Navigational Menu

Q & A: generating primes

Learn more physics!

Most recent answer: 01/23/2016
Q:
As we know about natural numbers,whole numbers and other one's. In case of natural and whole numbers there is a sequence for numbers that comes after a number for example in 1 by adding 1 we get 2nd natural by adding 2 we get 3rd natural number. My question is there a such sequence for prime numbers that without checking the divisibility of an extremely large number we can tell it is prime or not?????
- Saqib Rashid (age 20)
Pakistan
A:

There's no formula for generating the list of primes. There have been ways of generating the list, going back to the Sieve of Eratosthenes (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), but these are not as simple as generating the natural numbers. That Wikipedia article has a nice discussion of the complexity of the algorithms for generating long lists of primes.

Mike W.


(published on 01/23/2016)

Follow-up on this answer.