A Programmer’s Quest for Primes: Part 1 – Brute Force

4 03 2009

While trying to come up with something to program, I looked to prime numbers in my discrete math class and decided to make a simpler prime number calculator. The deeper I delve into the world of prime numbers the more interested I become. The building blocks of all numbers with plentiful applications in cryptography have captured my spare time recently. This is part 1 of my quest for calculating prime numbers. I have no real goal in this quest, other than to expand my knowledge of mathematics and sharpen my skills of programming; it’s the journey that matters, not the destination.

First off some math. What is a prime number?

Prime Number: A positive integer p greater than 1 is called prime if the only positive factors of p are 1 and p. A positive integer that is not prime is called composite.

For example, 42 is not prime, it can be written as the product of the factors 2 and 28. 28 isn’t prime either, it can be written as 2*14. 14 can be written as 2*7. What can 7 be written as? or 2? Nothing, these are primes. Now a useful theorem.

Fundamental Theorem of Arithmetic: every positive integer greater than 1 can be written uniquely as a prime or as a product of two or more primes.

That means 42 can be written as 2*2*2*7, all of which are prime numbers. 105 can be written as 3*5*7, all prime.

Now, how can you tell of a number is prime? Well, if the number is composite, that means it can be divided by some prime number. You can keep a list of prime numbers and then try and divide that number by them all. If it doesn’t divide by any prime numbers, it’s prime itself. For example, we find a list of prime numbers: 2, 3, 5, 7, 11. Now suppose we want to see if the number 13 is prime. We’d do the following,

13 % 2 == 0? If so prime.

13 % 3 == 0? If so prime.

13 % 5 == 0? If so prime.

13 % 7 == 0? If so prime.

13 % 11 == 0? If so prime.

None of these numbers can divide 13, so 13 is prime. When we get into prime numbers like 576,194,557 though, this process will be doing millions of checks on the prime numbers found before, which will be horribly slow.

A quick way to make a huge speed difference is use another handy theorem.

Theorem: If n is a positive composite integer, then n has a prime divisor less than or equal to sqrt(n).

So rather than checking if 576,194,557 is divisible by each prime found before it, we can just check if it’s divisible by any of the primes less than or equal to 24,004.

Before getting down to the programming, one more quick way to make it more efficient is to count by 2’s, since we know all prime numbers are odd. In fact, prime numbers always end in either 1, 3, 7, or 9. Increasing the number you’re checking for primeness by 2 every time can eliminate checking anything that ends with 0, 2, 4, 6, or 8.

Therefore,  a simple brute force method for finding primes: create an array (in the heap, because the stack will overflow), and store all the primes you find in it. Increase your candidate number by 2, try to divide it by all the primes in the list, and break out of the loop if you find a number that divides it or if you reach a prime larger than sqrt(candidate). The latter means it’s composite and the former means it’s prime. Keep doing this until you find as many primes as you like. My source code for such a program written in ANSI C can be found here, http://pherricoxide.jumbofx.com/code/simpleprimecalc.c. It’s well commented and should compile with any ANSI C compiler. This is the first of hopefully several prime calculators I’m going to write.

Using this program on a 1.4ghz Intel Core 2 Duo with 2GB RAM, the first 100 million primes are found in about 137 minutes.

The problem is, as the numbers get bigger, this program runs slower and slower. The graph below shows time plotted on the horizontal axis and number of primes found plotted on the vertical. You rapidly find primes in the beginning, but after a while it will inevitably take you long minutes just to find a few primes. Using this method, we hardly have to worry about running out of RAM, because by the time we get 2GB of data (around 200 million primes), the process will be going so slowly it will hardly be worth continuing the search, at least using this brute force method.

primes

Stay tuned for faster prime calculations with better code, better algorithms, and someday perhaps even some cluster computing, as I continue my quest for primes. Until then, here are some prime numbers to spot check your own prime calculating programs with.

1 millionth prime: 15,485,863 (found in 7 seconds)

5 millionth prime: 86,028,121 (found in 112 seconds)

10 millionth prime: 179424673 (found in 5 minutes)

20 millionth prime: 373,587,883 (found in 12 minutes)

30 millionth prime: 573,259,391

40 millionth prime: 776,531,401

50 millionth prime: 982,451,653 (found in 50 minutes)

60 millionth prime: 1,190,494,759

70 millionth prime: 1,400,305,337

80 millionth prime: 1,611,623,773

90 millionth prime: 1,824,261,409

100 millionth prime: 2,038,074,743 (found in 137 minutes)

Advertisements

Actions

Information

6 responses

15 03 2009
novelgentry

Prime numbers are so 1950. My brother, a co-worker, and I are trying to find a greater meaning / actual mathematical significance for Lychrel numbers and something we are calling Elcyclic numbers. What do we have so far? Not much, but it’s interesting nonetheless.

Seems like fairly uncharted territory as opposed to primes, which is perhaps what makes it a bit more interesting. Then again, primes actually have some sort of application, and mathematical significance as factors… but maybe one day so will Lychrels and Elcyclic numbers. Check it out: http://novelgentry.wordpress.com/2009/03/15/number-theory-drive-me-more-insane-why-dont-you/

14 10 2009
kammueller

I did the same kind of thing in Excel. Very slow, but kind of fun to crank out a couple million primes. One simple observation that I used, was that you don’t have to compare each number to each prime in the list of primes. Only those that are less than the square root of the number you are looking at.

Doing that should speed things up considerably, but you are still left with the memory problem.

10 01 2010
Max

to solve the memory problem, i used formulas to approximate highest number to be checked(can be found online), then created an array that represents 8/30ths of all consecutive numbers(eliminates multiples of 2,3,5)

6 07 2010
jeremy

seems like my recent project, I would suggest using sieve eratosthenes. There is also an Nth formula to find the approximate value of the nth prime that can be used to find an nth prime number quickly, although i’m not currently sure how it works. And because you are storing all the prime numbers you don’t actually need to test the next one if you find it using what you have correctly.

currently i believe your using a form of wheel factorization which is only efficient for small numbers as i found out when i wrote my own program, taking around a day to get to the 1 billionth prime number, although im sure i could make it much faster now because it only use a basic wheel factorization (I was reinventing the wheel one could say).
also if your looking for a way to try to check your prime numbers, try wolframalpha.com.
another great resource is http://primes.utm.edu/

6 07 2010
jeremy

oh wait theres a part 2 and 3 and 4… which cover everything basically i said. lol

12 08 2012
Mark Ross

1. If you’re using an array and the Sieve of Eratosthenes, then you don’t need to store the actual prime numbers. The array can represent whether the index at that location is prime by storing one of two different values, keeping things pretty simple. If you want to get even smarter, you could use a character array and simply store a ‘y’ or ‘n’ to hold your finding at each array location. This might let you reach numbers that you couldn’t when storing numeric values in the array. Even further down the road, you can use a ‘bit array’ which will let you process 8 times as many numbers as a character array will. The methods for a bit array are specialized, so you’ll have to study those.

2. When you want to ‘strike out’ the multiples of a discovered prime (call it p), you can start with p squared as the first number to strike off because any smaller composite of that prime number will already have been struck off when processing a smaller prime. You can also use 2p as your increment, since every other multiple will be divisible by 2.

Use this technique for any prime greater than 2. You’ll have to treat 2 as a special case at the beginning.

Using the above techniques, I’ve been able to check for primes up to around 879,000,000 with a java program that runs in under 30 seconds.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: