X

By using this website, you accept our use of cookies. We use cookies to offer you a better experience and to help your page work effectively.

Math18

Prime numbers

Content

What are prime numbers?

The prime numbers are natural numbers that are only divisible between themselves and 1.

Note: The number 1, by agreement, is not considered a prime number.


How do you know if a number is prime?

There are different ways to check if a number is prime, below we list some methods.

First method: Sieve of Eratosthenes

  1. Since the number 2 is a prime number and is an even number, any multiple of 2 is not a prime number, therefore, every number ending in 0, 2, 4, 6 or 8 is not a prime.
  2. Since the number 5 is a prime number and its multiples always end in 0 or 5, therefore, any number ending in 0 or 5 is not a prime.
  3. Check if the sum of the digits form a number divisible by 3, if it is divisible by 3 it is considered that it is not a prime number.
  4. Since the number 7 is a prime number we must calculate multiples.
  5. We have to continue successively obtaining the multiples of the following prime numbers, the limit is when the prime number squared exceeds the maximum number of which we want to know if it is a prime number.

Now we are going to know the prime numbers from 1 to 100 by applying the previous 5 rules and considering by agreement that 1 is not a prime number.

  • Grouping rule 1 and 2 together we first eliminate the numbers ending in 2,4,5,6,8 and 0.[Marking color = red]
  • Numbers that were not deleted are checked by applying rule 3, therefore, if the sum of their digits are divisible by "3" is removed from the table. [Marking color = orange]
  • The multiples of 7 are obtained (considering that they are less than 100) and are eliminated from the table. Multiples of 7: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98. [Marking color = yellow]
  • Since the table is up to the number 100 we must consider that the prime number squared to exceed our limit is no longer considered, in this case 11 x 11 = 121, therefore, 121> 100 and all the numbers that were not Marked are prime numbers.
  • 1 2 3 4 5 6 7 8 9 10
    11 12 13 14 15 16 17 18 19 20
    21 22 23 24 25 26 27 28 29 30
    31 32 33 34 35 36 37 38 39 40
    41 42 43 44 45 46 47 48 49 50
    51 52 53 54 55 56 57 58 59 60
    61 62 63 64 65 66 67 68 69 70
    71 72 73 74 75 76 77 78 79 80
    81 82 83 84 85 86 87 88 89 90
    91 92 93 94 95 96 97 98 99 100

    Prime numbers from 1 to 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

    Note: To know the prime numbers from 1 to 100 we only need to calculate the multiples of 2,3,5 and 7.

It is possible to simplify the procedure for Sieve of Eratosthenes, we must consider the following steps:

  1. Any number ending in 0, 2, 4, 6 or 8 is not prime, except number 2.
  2. Any number ending in 0 or 5 is not prime, except the number 5.
  3. To find the prime numbers of the following numbers we must squared and then the prime number to evaluate is multiplied by two, the result of the multiplication is added in sequence to obtain the numbers that must be discarded, for example:
    • The number 3, when square gives us the number 9 (9 is considered a number that is not prime), when multiplying 3 x 2 = 6 and later making a summation sequence we obtain the numbers that we must discard from the sieve: 9+6=15, 15+6=21, 21+6=27, 27+6=33 and so on.
    • The number 7, when squared gives us the number 49 (49 is considered a non-prime number), by multiplying 7 x 2 = 14 and then making a summation sequence we get the numbers that we must discard from the screen: 49 +14 = 63, 63 + 14 = 77, 77 + 14 = 91

Note: It is not necessary to find the multiples before the square of the prime number, since they were discarded by the previous prime number or numbers, for that reason in number 3 starts at 9 and at number 7 starts from 49.

Second method: Wilson's theorem

Wilson's theorem mentions: A natural number n> 1 is prime if and only if the factorial (n - 1)! + 1 is divisible by n.

(n - 1)! + 1 /
n

The advantage of using Wilson's theorem is that we can easily know if a specific number is prime, suppose we want to know if a number is prime, for example n = 12 and n = 13.

  • For n = 12, substituting in Wilson's theorem formula:
    (12 - 1)! + 1 /
    12
    = 3326400.083333

    The result has decimals, it is considered that the number is not prime.

  • For n = 13, substituting in Wilson's theorem formula:
    (13 - 1)! + 1 /
    13
    = 36846277

    The result is an integer, it is considered a prime number.