Prime Numbers

[Aange10]

I know this is a bit lackluster on my end, but could anybody explain a basic way of finding out which numbers are prime?

I know how to do it by hand, but I mean in programming. Something short of going through every number before it and seeing if it can go into the number.


This seems to be a popular thing that is requested of people, and I'm doing the projects @ http://projecteuler.net/problems .

^ Great site for anybody loooking to do some fun problems!

[A.J]

Hello,

There are many ways of determining which numbers are prime. One naive way to determine whether a given number x is prime is to check whether it is divisible by any number from 2 to x-1 (if isn't divisible by any of those numbers, then it is prime). One way to speed this up is to realize that every composite number has a prime factor that is less than the sqrt of itself (why is this so?). Thus you only have to check for divisibility uptil floor(sqrt(x)).

Another common exercise is to find all the prime numbers in a given range of numbers. This is particularly useful in PE (I've probably had to do this _at_least_ 100 times). One way of 'sieving' for prime numbers in a range is doing the following:

Say you want to find all the prime numbers from 1 - 10. First list out the numbers from 2 - 10 (as you know that 1 isn't prime nor is it composite). Then for each number that remains in the list, cross out all of its multiples from the list. Continue doing this for all the numbers uptil the square root of 10 (once again, why do we stop here? something to think about). Thus, initially we'd have:
2, 3, 4, 5, 6, 7, 8, 9, 10

Since the first number in our list is a 2, we cross out all of its multiples from the list, leaving us:
2, 3, 5, 7, 9

Now the next number in our list is a 3, so we cross out its multiples:
2, 3, 5, 7

At this point we stop, as the next number (a 5) is greater than the square root of 10. Now the list consists of all the prime numbers in the range from 1 - 10. This method, called the Sieve of Eratosthenes, is really useful (especially in PE), as it provides a quick way to determine all the primes <= some number. The reason this works is because of the same reason as before: every composite number consists of a prime factor that is less than square root of itself. Thus every composite number will have been removed from the list at some point, leaving you with only the prime numbers.

Here are a few links that might help you: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

There are other sieves as well, but this one should suffice for most of the problems that require primes in PE.

I hope this clears things up a little.

[bl0ckeduser]

There are several algorithms. Two simple ones are:

1. The Sieve of Eratosthenes
Fairly simple. They taught it to me in elementary/highschool. See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. You can implement it in roughly 30 lines quite easily. C implementation:

code:

#include <stdio.h> #define MAX 64 main() {         char* sieve;         int k, n;         if(!(sieve = malloc(MAX))) return 1;         memset(sieve, 0, MAX);         /* 1 isn't prime */         sieve[1] = 1;         k = 1;         while(k++ < MAX) {                 n = 2;                 while(n * k <= MAX) {                         sieve[n*k] = 1;                         ++n;                 }         }                 k = 0;         while(k++ < MAX)                 if(!sieve[k])                         printf("%d\n", k);         return 0; }

2. Going through all the factor candidates
Given a number, you check that it doesn't divide evenly by any of its potential factors. The largest factor candidate is sqrt(n), if not ceil(sqrt(n)). This algorithm can be implemented in about 5 lines. C implementation:

code:

#include <stdio.h> #include <math.h>       /* sqrt() */ int prime(int n) {         int f = 2;         while(f <= sqrt(n))                 if(n % f++ == 0)                         return 0;         return n > 1;   /* 1 isn't prime */ } main() {         int i;         for(i = 1; i < 30; i++)                 if(prime(i))                         printf("%d\n", i);         return 0; }

That being said, there are fancier, faster, better algorithms, as well as optimizations which can be made to the two simple ones I have outlined, potentially making them quite faster. (I believe ProjectEuler has PDFs about how to optimize the factor-candidate algorithm). And as with any set of algorithms, each has its specific advantages and disadvantages.[/list]

[Aange10]

Thanks to you both. And thankyou AJ, I understand.


And we use the square root because that is the 'middle' point for our multiples, before we start looping backwards.


For instance finding the factors of 81 we would say:

1 and 81
3 and 27
9 and 9
----sqrt-----
27 and 3
81 and 1


There would be no reason to go past 9 (the square root) because of the associative property of multiplication.

[Dreadnought]

Aange10 wrote:

There would be no reason to go past 9 (the square root) because of the associative property of multiplication.

I think you mean the commutative property of multiplication on real numbers.
The associative property says that

code:

(A * B) * C = A * (B * C)       for all A, B and C

The commutative property says that

code:

A * B = B * A      for all A and B

[A.J]

@Aange10- Well, think about it this way: if all the prime factors of a composite number were greater than the square root, then since every composite number hast at least two prime factors, the product of the prime factors will be greater than the number itself (which isn't possible). Thus the composite number must have some prime factor that's less than or equal to the square root of the number.

[Aange10]

My code works:

Python:

def findPrime (maxNum):     listOfNumbers = range (3, maxNum, 2) # All even numbers are except 2 composite     # Go through each place in the list     for divBy in listOfNumbers:         currentIndex = -1         # If it divides evenly, take it out         for restOfList in listOfNumbers:             currentIndex += 1             if restOfList % divBy == 0:                 if restOfList != divBy: # make sure it's not x/x                     del listOfNumbers[currentIndex]     return [2] + listOfNumbers # We didn't add a 2 at the beginning

Given that you want all of the primes below a certain number. However in my current question it wants all of the sum of all prime numbers below 2,000,000.

This method doesn't seem to cut the 60 second rule for the website. That, and it's taking all the power on my pretty well built PC.

(And I know to get the sum just to use 'return sum(listOfNumbers))

Is there another algorithm you might could suggest? I'll also do some researching


EDIT: It finished after 4500 seconds (75 minutes) and gave me 142,913,828,922 which was correct.

[Aange10]

Aange10 @ 3/6/2012, 7:12 pm wrote:

My code works:

Python:

def findPrime (maxNum):     listOfNumbers = range (3, maxNum, 2) # All even numbers are except 2 composite     # Go through each place in the list     for divBy in listOfNumbers:         currentIndex = -1         # If it divides evenly, take it out         for restOfList in listOfNumbers:             currentIndex += 1             if restOfList % divBy == 0:                 if restOfList != divBy: # make sure it's not x/x                     del listOfNumbers[currentIndex]     return [2] + listOfNumbers # We didn't add a 2 at the beginning

Given that you want all of the primes below a certain number. However in my current question it wants all of the sum of all prime numbers below 2,000,000.

This method doesn't seem to cut the 60 second rule for the website. That, and it's taking all the power on my pretty well built PC.

(And I know to get the sum just to use 'return sum(listOfNumbers))

Is there another algorithm you might could suggest? I'll also do some researching


EDIT: It finished after 6116 seconds (102 minutes) and gave me 142,913,828,922 which was correct.

[Dreadnought]

Python:

for divBy in listOfNumbers:

I'm not very familiar with python, but it seems you're going through the entire list of numbers all the way up to 2,000,000. You should only have to go up to the square root. Afterwards all composite numbers will already be gone.

I would set up a list of 2,000,000 ones. Then use nested for loops to set all composite numbers to zero (many will be set to zero more than once but that's fine). At the end just sum up the indices of value 1. That should be doable in ~ 1 second.

[A.J]

You seem to be iterating through all the elements in the list. You should only go through elements that are left in the list. One way to do this is to use an array of boolean to determine whether a number is in the list or not:

code:

list: array of boolean from 2 to 2000000 set list[i] = true for i from 2 to 2000000 for i: 2 ... floor(sqrt(2000000))     if (list[i] = true)         for j : i*i .. 2000000, by i (i.e. increment j by i each time)             list[j] = false

Notice that you only have to start at i*i when crossing out multiples from the list (and not 2*i. Think about why this is so).

[Aange10]

dreadNought wrote:

I'm not very familiar with python, but it seems you're going through the entire list of numbers all the way up to 2,000,000. You should only have to go up to the square root. Afterwards all composite numbers will already be gone.

Ermm I think you misunderstood what i'm doing. I'm finding every prime number up to 2,000,000. Doing the square root wouldn't work.

For example, if I wanted all the primes up to 25 but stopped at 5 (the sqrt), well, I wouldn't get all of them (17, 13, etc.)

Quote:

I would set up a list of 2,000,000 ones. Then use nested for loops to set all composite numbers to zero (many will be set to zero more than once but that's fine). At the end just sum up the indices of value 1. That should be doable in ~ 1 second. Smile

Hmm, smart. Because the index is already = the value, so no reason to make the value a big number when you already have it as the index.

[Dreadnought]

I meant that it was useless to strike out multiples of primes greater than the square root since they will already have been taken care of.

[Aange10]

Dreadnought @ 3/6/2012, 10:30 pm wrote:

I meant that it was useless to strike out multiples of primes greater than the square root since they will already have been taken care of.

Hmm. In that case, I don't understand.

[Dreadnought]

Suppose I want to find all primes from 2 to 100.
I write them all down on a piece of paper, then, beginning at 2 I strike out all multiples of 2 starting at 2^2 (4) then of 3 starting at 3^2 (9) then of 5 (4 has already been struck out) and of 7 always starting at the square of the prime.

Since 10 is the square root of 100 and I have no more primes less than 10, I am done. All composite numbers less than 100 have at least one of 2,3,5 or 7 in their prime factors. (A.J mentioned this)

[Aange10]

Oh. I guess I didn't realize that. That makes sense though. Thanks for the help you guys!


EDIT: When i posted I hadn't seen AJ's post.
EDIT2: In response to AJ: Is it because nothing before i*i is going to be divisible by i?