-----------------------------------

Aange10

Sun Jun 03, 2012 3:14 pm


Prime Numbers

-----------------------------------

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

Sun Jun 03, 2012 3:51 pm


RE:Prime Numbers

-----------------------------------

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