Hello fellow learners! Today we’re going to learn about prime numbers and everything related to it such as “What is a prime number? What’s the largest known prime? How can you find prime numbers? How can you decide if a number is prime? What’s the ‘Sieve of Eratosthenes’? So without wasting any more time, let’s start learning!
What Is A Prime Number?
A prime number, the building block of all numbers, is a positive integer, which can be divided, but only by itself, by 1 and without a remainder. In other words, a prime number is a whole number that is not made by multiplying other whole numbers. For example, 5 is a prime number because it’s not divisible by any number except 5 and 1. And 10 isn’t a prime number because it can be divided evenly by 2 and 5.
In case you are wondering, 1 is not a prime number as it has only one factor – 1. Prime numbers need to have two factors- exactly two. When a number has more than two factors, it’s called a composite number.
The downside of the prime number is that there is no formula to help you determine whether a number is prime or not! So you need to do everything manually. While it’s quite easy to find the first few prime numbers, things get difficult as you reach larger numbers.
History Of Prime Numbers:
Prime numbers have been in use for thousands of years. Some experts say that ancient Egyptians were the pioneers of prime numbers, but it was the ancient Greeks who studied it in depth. The mathematicians of the Pythagoras’ school took immense interest in numbers for their numerological and mystical properties. They even understood the primality idea well enough and showed immense interest in perfect and amicable numbers.
“Elements” by Euclid, which was published at around 300 B.C, mentioned several instances of prime numbers. The 9th Book of “Elements” states that there are infinite prime members. In fact, Euclid also proved the Fundamental Theorem of Arithmetic where every integer is written as a prime number in a unique way. In the book, Euclid also showed how to create a perfect number using Mersenne primes. For those wondering, a Mersenne prime is a prime number calculated using the 2n-1 equation.
Eratosthenes also created an algorithm to calculate the prime numbers, which is known as the Sieve of Eratosthenes. We’ll talk about it in detail below.
What followed was the Dark Ages, which suppressed since and intellect so much that the works on prime numbers were halted.
In the 17th century, renowned mathematicians like Gauss, Euler, Fermat, and more examined patterns existing within prime numbers. Fermat proved Albert Girard’s speculation and even devised a new method of factorizing large numbers. What he proved later came to be known as “Fermat’s Little Theorem”.
Euler extended Fermat’s Little Theorem and introduced his own Euler φ-function. He was also the first one to prove that the number theory could be studied using the tool of analysis. And you would be surprised to know that in the process he founded the subject of Analytic Number Theory.
These theories and conjectures revolutionized Math, but some are yet to be proven even today.
How To Find Out A Prime Number?
To find a prime number, you have to first try to divide by a number by 2 and see if you’re getting a whole number. If you get a whole number, it’s not a prime number. When you don’t get a whole number, you should next try to divide the number by prime numbers, for example, 3,5,7,11, 13, 17, 19 and so on.
For example, 8 is not a prime number because it is divisible by 2. But 73 is a prime number because it’s not divisible by any number and no other whole number multiply together to make it.
Finding a prime number because more difficult, particularly if there’s a set amount of time. A computer is generally used to test large numbers to see if they are prime not. But since there’s no limit as to how large a prime number can be, it because of a huge task even for the most powerful supercomputers.
Prime Numbers Table:
Here’s a table of all the prime numbers up to 1000 for your reference:
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 101 103 107 109
113 127 131 137 139 149 151 157 163 167
173 179 181 191 193 197 199 211 223 227
229 233 239 241 251 257 263 269 271 277
281 283 293 307 311 313 317 331 337 347
349 353 359 367 373 379 383 389 397 401
409 419 421 431 433 439 443 449 457 461
463 467 479 487 491 499 503 509 521 523
541 547 557 563 569 571 577 587 593 599
601 607 613 617 619 631 641 643 647 653
659 661 673 677 683 691 701 709 719 727
733 739 743 751 757 761 769 773 787 797
809 811 821 823 827 829 839 853 857 859
863 877 881 883 887 907 911 919 929 937
941 947 953 967 971 977 983 991 997
The Sieve of Eratosthenes:
Over the years, we’ve come across various algorithms to generate the largest prime number, but none has been definite so far. But if you’re looking to find smaller prime numbers, the Sieve of Eratosthenes could be of immense help.
Eratosthenes had devised a ‘sieve’ to discover prime numbers and make things easier for students and learners like you and me.
A sieve, as we all know, is a strainer used to drain pasta and noodles. The water drains out completely from the holes of the sieve, leaving just the food behind. Similarly, the sieve devised by Eratosthenes drains out composite or multiples of a number and discard them, which will leave us prime numbers.
The Sieve of Eratosthenes works until the squares of the number testing are greater than the last number on the grid, for instance, 100. Hence, 11 sq = 121 and 121 is greater than 100, we will stop at 11.
To use the sieve of Eratosthenes, you need to make a chart like below
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
Steps For The Sieve Of Eratosthenes:
- First, you need to cross out 1 as it’s not a prime number.
- Make a circle around 2 as it’s the smallest positive even prime number. Next, you need to cross out every second number or every multiple of 2.
- Now make a circle around 3, which is the next open-prime number. Now you have to cross out every third number or every multiple of three. In the process, you will notice that some numbers like 6 or 12 will already be crossed out as they are also multiple of 2.
- Now we’ll move to 5, which is the next open-prime number as 4 has already been crossed out. Make a circle around 5 and cross out every 5th number or all the multiples of 5.
You need to continue doing so through 100 until all the numbers are either circled or crossed out. The circled number will be the prime numbers/
Prime Numbers And Encryption:
Way back in 1978, three researchers found a way to scramble and unscramble coded messages using prime numbers, which paved way for Internet security years later. Today, prime numbers are placed at the heart of electronic commerce, which has simplified secure transactions. The security of this cryptography is dependent on the difficulty of factoring large composite numbers, which is a result of two prime numbers. And two primes are considered safe if they are 2048 bits long, as the product of these two primes would be 1234 decimal digits.
Prime Numbers In Nature:
As surprising as it may sound, prime numbers even show up in nature. There a reason why Cicadas spend most of their time hiding and reappear to mate every 13 and 17 years. Cicadas reproduce in cycles because it minimizes the chances of interactions with the predator. If by chance, the predator’s reproductive cycle divides the cicada’s cycle even, the predator will hatch at the same time as a cicada, at some point or the other. Hence, cicadas follow a prime number reproductive cycle to minimize contact with the predators.
Facts About Prime Numbers:
Below we’re sharing some fun facts about prime numbers.
- 2 is the only even prime number and all the other even numbers can be divided by 2.
- There’s no prime number greater than 5 ends in 4. Any number that is greater than 5 and ends in a five can be divided by 5.
- 0 and 1 are not considered prime numbers and except for these numbers, a number is either a composite or a prime number.
- Until now, people have been unable to find the largest prime number, but you’ll be surprised to know that the efforts are still going on. In fact, the “Guinness Book” includes a list of 5000 largest known prime numbers and the smaller ones of the selected forms. So you can say that prime numbers are a hot topic!
- The largest prime number to be ever discovered is 2 raised to the 57,885,161st power minus 1, or 257,885,161 – 1. The number is 17,425,170 digits long and was discovered by Curtis Cooper, a mathematician from the University of Central Missouri. He was a part of a huge number devoted to finding large prime numbers.
We really hope you enjoyed learning about prime numbers as much as we did. We would strongly recommend you to try the Sieve of Eratosthenes and let us know if you found the prime numbers or not!