A Fun Fact About Prime Numbers
Take a random integer: let’s say 17783. Is it a prime number? (yes)
If you had to go about checking whether or not that was a prime number, how many numbers would you have to divide it by before you could be sure it was prime? That’s a more fun question.
The first instinct is to say, 17782, since you need to be sure that every number lower than 17783 doesn’t divide it.
Of course, it quickly becomes obvious that you only need to test other prime numbers, since those would necessarily show up in the prime factorization. Even then, that’s too many. Why test, for example, 17761 (the next prime below 17783) since it can’t possibly divide a number so close. It’s tempting to jump to the idea of testing primes below n/2. Even that turns out to be more than necessary though.
In fact, you only need to test up to the square root of n in order to determine that n is prime. In the case of 17783, that turns out to be only 32 numbers (the 32 primes below 133, which is close to the square root on 17783).
Then again, you could always just look it up here.
-
danhefferan liked this
-
30daysatatime posted this
