The first thing that's got to be said. There is a lot to learn about primes, so let's start from the very beginning. A prime is any positive whole number with only and exactly 2 factors, being 1 and itself. After hearing this, many people come to believe that 1 is prime, but by definition this can not be true. This is thought because 1 can only be divided by 1 and itself(1), but by definition a prime is a number with 2 factors, whereas 1 only has 1 factor. It is also not composite number, as a composite number, rather than just being a number which is not prime, is a number with more than 2 factors. 1 is in its own class, and is known as the multiplicative identity. At this point, primes seem pretty simple, as well as pretty useless. Wrong. Primes are extremely relevant and useful in multiple areas of mathematics, as we will be learning soon. But first, how do you find primes?
How to find prime numbers:
There are several processes that can be used to find prime numbers, and we will be covering the most common of which in this lesson. This method is known as the Sieve of Eratosthenes and is used to find all prime number up to a certain limit through a process of elimination. Say you are looking for all primes with a limit of 100. Begin from 2, as 1 is not prime, as concluded earlier, and 2 must be prime, as there are no possible factors of 2 excepting 1and 2, making it prime. So 2 is prime. But then you can conclude that all multiples of 2 are composite, as they are at the very least multiples of 1, 2 and themselves. Next, you can see that 3 is now prime as it is not a multiple of 2. Then you can eliminate all multiples of 3. You can than do the same with 5, 7, 11, etc, continuing with all values that have not been crossed out one by one. Through this you can find that there are in fact 25 primes up to 100 being 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89 and 97.
This is probably the best method for finding all prime numbers, but if you are simply looking for large primes, it is quite a slow and inefficient system. This can be solved using a fact being that not all of the time but quite often, 2 to the power of a prime number minus 1 is a prime number. For example, 2^7-1 = 127, which is prime, but 2^11 - 1 = 2047 = 23 x 89. In order to test whether it is prime or not, you simply use the original method of dividing the number by all primes below the square root. This is the standard method used by supercomputers to find the largest prime numbers. As of September 18, 2019, the largest known prime number is 2^82589933 - 1, which when written in full is 24,862,048 digits long. To put this into perspective, if someone was to recite this at one digit per second, they would be near the end of the 288th day when they finished.This method is quite good for finding larger primes, but there is no guarantee that the result will in fact be prime, so you must test this using the following method. You start with the number in question, which can be any positive integer, for example 63, and you find the positive square root of this number, rounded to the nearest whole number. In this case, the square root of 63 isn't a whole number but can be rounded to the nearest integer, being 8. Now, we divide the original number, 63, by every prime number below the square root previously calculated. If there are no whole number results, the number is prime. In the example, dividing 63 by 2 is a decimal, at 31.5, but dividing by 3 gives a result of 21, meaning 63 is not prime. You would also have found this again when dividing by 7, which gives a result of 9, but there is no reason to continue past 3 in the example. Given, this requires you to know the prime number below the square root, but this step is simply a secondary step in order to prove that larger numbers are prime, and the primes below the said square root would already have been found if the first discussed process is followed.
Comments
Post a Comment