A prime number is a number greater that one which can be evenly divided only by one and itself. For instance, we can divide 3 by 2 and we’d get 1.5, but that wouldn’t be even. We can divide 3 by 3 and get 1; that’s an even division (even though the answer is odd), and we can divide 3 by 1 and get 3—that’s also an even division. Three, then, is an example of a prime number.
Are primes odd?
Some odd numbers are prime, but not all odd numbers are prime, although we can say with a good level of confidence that almost all prime numbers are odd (the exception being 2, of course).
The assertion “almost all primes are odd” is a little odd, because primes aren’t really odd, they’re sort-of beautiful. That's probably one of the reasons why mathematicians give them so much attention.
Eratosthenes
The Sieve of Eratosthenes (pronunciation here for those to-which this is Greek) is an algorithm for finding prime numbers. I make no claim to be in any way prime-number-generation literate, so, as a disclaimer, this is the only way I know of to find primes short of an ugly brute-force approach.
In short, it goes like this:
Choose a number n up-to-which you wish to find all prime numbers;
Iterate through the numbers 2 to √n for each value (i):
2.1 Starting at the square of the value (i × i), “cross off” values by repeatedly doing an i-sized “hop” to the subsequent value, until i is greater than the square-root of n (√n);
For example, this C# snippet demonstrates the algorithm for a small n:
var upTo = 31;
var numbers = Enumerable.Range(2, upTo-1).ToList();
var end = (int)Math.Sqrt(upTo);
for (int i=2; i < end; i++) {
for (int j=i*i; j <= upTo; j+=i) {
numbers.Remove(j);
}
}
foreach (var p in numbers)
Console.WriteLine(p);
s m t w t f s
2 3 5
7 11
13 17 19
23
29 31
Comments !