You simply have to have a list of all the primes that are lower than it, and check to see if it divides evenly by any of them. (and as a shortcut, only needing to test those that are half the size or less) So verifying a number is prime is monumentally easier than finding a new undiscovered prime.
Actually you only need to test primes up to the square root of the number you are checking. Numbers up to half the size could include divisors with prime factors you have already checked.
OK. What "those" referred to was unclear to me. Even so, primes up to the square root of n are fewer in number than primes half the size or less than n, so it would be a "shorter cut":
"The simplest primality test is trial division: Given an input number n, check whether any prime integer m from 2 to √n evenly divides n (the division leaves no remainder). If n is divisible by any m then n is composite, otherwise it is prime."
—
Primality Test "Half the size or less" is a useful shortcut if you want to check all the potential divisors of a number and eliminate the non-prime ones.
For example, is 17 prime? 17/2 = 8.5 so check 2,3,4,5,6,7,8. Eliminate evens (because 17 is not even—not divisible by 2—so an even cannot divide it) and check 2,3,7.
OR
√17= 4-ish, so check 2,3,4; eliminate the even 4 and check 2 and 3. Fewer checks.
When testing large numbers, the "fewer checks" can be considerable.
Perhaps Virtual1 was saying the same thing; I just needed to see it in more detail, so all of you reading this benefit/suffer from my examination.
