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.
