My understanding is that most (all?) newly-discovered large prime numbers are found via computer programs. I tried reading upon the methodology to find those numbers but I got lost in the mathematical formulas. My guess is it’s not as simple as “find an odd number then start dividing it by all numbers that are approximately 50% of that number or less, and send an alert when you run the whole series and always get remainders.” I mean…that would work but it seems like the slowest and least efficient way to find primes. Is here some way of explaining this that doesn’t rely on me understanding a formula?
In: Mathematics
You are correct that (as far as we know) the only way to know for sure that a number is prime is to do something like the whole square root of the number thing.
But there are some tricks around it.
For starters, there’s some algorithms like the [Miller-Rabin test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test).
You run it many times on a number.
Each time your run it, it either confirms that the number is not prime, or that it’s maybe a prime.
So if you run it many many times, you can be pretty sure that a number is a prime number, but don’t have to crunch every single number to the square root.
A surprising amount of real world encryption works on numbers we only suspect as prime, because of this algorithm.
There’s also [prime-counting functions](https://en.wikipedia.org/wiki/Prime-counting_function) which tell you how many prime numbers there are less than a particular number, but just not what the prime numbers are.
So we can focus our efforts where we know prime numbers are going to be.
~~Also if we ever get every single prime number in order, we can make a brand new prime number, by multiplying them all up and adding 1.
There are likely to be many primes in between the last one we found and the new one we made.~~
Latest Answers