Finding new prime numbers?

Question

I would think it would be simple to make up a program to find prime numbers... I mean the only numbers possible end in 1,3,7,9 excluding the first 2 and 5 of course, then it is just dividing a number by all the prime numbers less then half the number you are checking... I would think the only problem would be time and storage space.

Answer 1

First, when using the sieve method, as you propose, you only need to go to the *square root* of the number, not to half. Any factor above the square root will have another factor below the square root, so you don't have to go any further.

The sieve method works well up to a point. I once wrote a program to figure the first 50,000 primes and it ran over night. In the morning I had a printout that was nearly 800 pages. (I should have put more than one prime on a line, by the way).

As you can imagine, the time to find each prime number grows exponentially. You can find the first 100 in a split second, and the next 100 in a little more time, but by the time you are up into lots of digits it takes a long time.

There are a special class of primes called Mersenne primes of the form 2^p - 1, where p itself is another prime. There are some efficient algorithms to sort through possible "candidate" Mersenne primes and even these algorithms take lots of times.

Currently there are thousands of standard PCs working together as a "distributed super computer" searching for the next Mersenne prime and that is taking some time. The last one was found several months back (Sept 2006) and the one before that was in Dec 2005. So it is taking months and months to find even single primes, not just minutes. To their credit, we are talking about prime numbers that are approaching 10 million digits.

The issues are partially storage, but fall more on computational efficiency, CPU speed and available time. Current estimates of finding large primes are as follows:
a 10,000,000 digit prime, sometime this year,
a 100,000,000 digit prime by early 2015, and
a 1,000,000,000 digit prime by 2024.

As you can see, given all the time in the world we could find lots of primes, but because the time needed increases exponentially as you aim for bigger and bigger primes, at some point it exceeds human lifetimes.

Answer 2

If you are looking to find the next prime number after a known set of prime numbers, then you are sort of right. Starting from N = 5, you can alternately increment N by 2 and 4, thereby skipping 2/3 of all numbers. Incrementing alternately by 2 and 4 skips all the numbers divisible by 2 and 3.

5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,...

And as a previous poster mentioned, you only need to test N by the set of prime number less than or equal to the square root of N. If you incremented using the 2-4 step method, you wouldn't even need to test N against 2 and 3. You would only need to test N against the set of prime numbers, {5,7,..(Pn<=√N)}. By doing these two things, you would eliminate (8/3)N steps when creating your set of prime numbers compared to iterating from 2 to N in increments of 1.

This is a good algorithm for finding relatively small prime numbers, however the larger N gets the more likely N is going to be divisible by a small prime number.

eg.
// Numbers taken from the list above.
N = 25 // Divisible by 5.
N = 35 // Divisible by 5 and 7.

If you were to continue this way, you will notice a pattern as far as what N is divisible by.

5 * 5 = 25
5 * 7 = 35
7 * 7 = 49
5 * 11 = 55
5 * 13 = 65
7 * 11 = 77
5 * 17 = 85

At large values of N, this type of algorithm becomes horribly inefficient for finding the next prime. At that point, you start getting into some complicated math to make an efficient algorithm.

Answer 3

It's easy to find prime numbers. You can pick a 100-digit odd number at random and test it; if it isn't prime you just pick another one. You'll find a prime fairly soon. These numbers are useful for coding programs.

It's not so easy to find a prime number bigger than any ever found before. Prime numbers get rarer as you go to bigger numbers, so picking one at random won't work. You need to look at particular types of number as being more likely to be prime, such as the 2^m - 1 numbers. Secondly, you won't have time to test if by dividing by every possible smaller number, as there isn't enough time left in the life of the earth to do that. So you have to devise a mathematical method for proving that the number is prime.

Answer 4

What on earth could make you think that you were the first person to have this idea? There are five or six books you should read, or try to read, before spouting such juvenile nonsense.

Anyway, with modern PCs, your method starts to run out of steam at primes of around 17 or 18 digits. Using university math, instead of high school math, there are better methods which have absolutely no problem in churning out guaranteed primes of 100 to 150 digits, as required for modern internet security methods, and they could be pushed up to around 600 digits.

Answer 5

No it is not an easy task as it is not a pattern with reccurenes.

LARGE (meant realy really really large) prime numbers are used in encoding and you can make money by find ones over 1000000 digits long.

Noones has ever come up with a tangible way of calculating prime numbers quickly.

This is where the Riemann hypothesis comes in, it is a conjecture that would be it possible to calculate prime numbers, but noones has solve it yet. A 1000000 dollar prize has been offered for its solution.

Answer 6

Actually you only need to try all prime numbers less than the square root of the number in question. It's been done. As numbers get really big, it starts taking a lot of computing power.

Answer 7

Your method works fine up to a point. Let's say it takes your computer one second to test a number close to a billion. Then, it will take about 1000 times as many calculations to test a number close to 10^15, a million times as many calculations to test a number close to 10^21, and a billion times as many calculations to test a number close to 10^27.

Now, a billion seconds is over 31 years - do you think there is any way you could test a number close to 10^27 in a reasonable length of time? And that's "just" a 27-digit number - how would you ever test a 50-digit or 100-digit number??

Answer 8

making a prog for finding prime numbers is not a big deal

Step1: [starting from any number] e.g. n
Step2: divide n [by a series of numbers i.e.] n-1 -- 2
Step: if any divides means not a prime else a prime.

Answer 9

there was a computer that was programmed to perform a similar task. it was to calculate pi to the infinite decimal space. after a short time, it stopped. the screen cleared. and a single word question appeard. why? the computer was immediately unplugged and dismantled. so... it's really not a good idea to let a computer sit there and just crunch numbers for our ammusement. because, as most science minded individuals will tell you, math is the universal language.

Answer 10

i wrote a program to do just that a long time ago. the computer couldnt handle it for very long, and they've gotten WAY farther than it did lol.

wrldzgr8stdad: please dont talk about science after spewing that bullshit...sagan would be spinning in his grave if he could read that :-/