Surely, a number of sufficient size would be divisible by a lower number at some point? A monster of a number with thousands, or even trillions, of digits would surely have to be so large, and the amount of numbers below it so plentiful, that something should be able to divide into it evenly? But the answer is no, there are an infinite number of primes and the proof is actually quite simple to walk through.
I found this concept difficult to grasp for a few reasons but it is nonetheless true. One more final point before we actually dive in and open up a spreadsheet: there are an infinite number of prime numbers. I feel that this is important to note because later on I will be using some shortcuts and they won’t make sense unless you have an understanding of primes and how they relate to composite numbers. Primes are the bricks used to build all the numbers you see around you. For that very reason, every single natural number can be factored down to its prime factors, run a few examples yourself if you like but every single natural number in existence can be expressed as the multiplication of primes unless of course the natural number in question is itself prime. Think of primes as the smallest, indivisible pieces used to construct composite numbers. 431 is a prime number so lets multiply that by a 2, then a 4 then a 6.Īnd what are the prime factors for 20,688?Īs you can see there are a lot of 2’s and a 3 but also the original 431 is a prime factor as well, this must be by definition because we built a composite using 431 and therefore, as we deconstruct the composite number the prime we used must come out wholly intact. How about a random, large number as an example. But what about 7 x 4, this results in 28 which can be factored down to 7 x 2 x 2. Take for example 7 x 3, the result is 21 and the prime factors of 21 are indeed 7 and 3. Perhaps it is easier to think about starting at the bottom, imagine taking a small prime number and multiplying that number by any other number of your choice, the result of that multiplication will be a composite number and one of its prime factors will be the prime that you had chosen. This can continue until the factors themselves are not divisible by smaller numbers and of course we call those primes. Every composite number will have prime factors and that should make some sort of intuitive sense because if a number is not prime it is divisible by other numbers and therefore it can be written as a factor of other numbers. In this case, the composite number 542 can be broken down into its prime factors of 2 and 271 (271 is a prime number and therefore cannot be factored into smaller numbers). (This can be read as 2 x 3 gets you to six). Here is an example of a factor tree for the number 6, you can see it is broken down into its prime factors. Six is not prime since it can be divided into evenly by both 2 and 3. Or, as Wikipedia has it: “is a natural number greater than 1 that has no positive divisors other than 1 and itself.” Every other number is considered a composite because they are composed of prime numbers. Prime numbers are numbers that are only evenly divisible by 1 and themselves. And speaking of prime numbers, I would like to briefly introduce them now because I do not want to gloss over anything from the beginning, this way the logic will make sense for when we actually begin building. The sieve will be able to spit out all the prime numbers between 2 and an arbitrarily large number of the user’s choosing.
#List of prime numbers to 10000 excel how to#
I will be explaining how to build something known as the Sieve of Eratosthenes, which I will explain in detail later.
Everything in this blog post will be about those uniquely fascinating numbers known as prime numbers.