What are prime numbers exactly? Prime numbers are numbers that can be divided, without a remainder, only by itself and by 1. For example, first odd number is number 2. 2 can only be divided by 1 and 2. Second number is 3, third 5 and so on… How can you determine whether the number is prime or not? First you divide it by 2 and see if you have a remainder, if you don’t, your number is not a prime. If there is a remainder that means that that number is not divisible by 2, and then you try it with 3 and continue until you get to a number you get when you divide your starting number by two.
For example number 7 is a prime number, because it can be divided only by one and 7, but 4 is not a prime number because, other than 1 and 4, can also be divided by 2.
Zero and one are not considered prime numbers. This is because, by the definition, prime numbers have exactly two divisors.
Sieve of Eratosthenes
What if you want to write down as many primes as you want? For the small primes, the most efficient way is the Sieve of Eratosthenes.
For example, if you’d like to find all the primes less than or equal to 30, first list the numbers from 2 to 30.
The first number is 2. 2 is a prime number. This means that we’ll leave them, and mark him blue. Cross out all of the multiples of the number 2, we’ll paint them gray.
Second one is number 3. This number is also a prime number, so we’ll again mark 3 with blue color, and cross out its multiples.
You continue this procedure. And in the end you’re left with:
That means that the prime numbers from 1 to 30 are: 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.
By the Fundamental Theorem of Arithmetic every positive integer greater than one can be written uniquely as a product of primes, with the prime factors in the product written in order of decreasing size. Knowing this theorem, we know the most important use of primes. We can learn a lot about certain integer if we know its prime divisors. It’s just like when you have a big problem that you’d like to solve – it is in your best interest to divide it into smaller problems.