Take a positive integer x. How can we find all the prime numbers not exceeding x? There's a method called the Sieve of Eratosthenes, which dates back to ancient Greece. The steps of the Sieve of Eratosthenes are as follows: First, list all integers from 2 to x, keeping 2 and eliminating all multiples of 2. Second, in the remaining sequence, the prime number following 2 is 3; keep 3 and eliminate all multiples of 3. Third, in the remaining sequence, the prime number following 3 is 5; keep 5 and eliminate all multiples of 5. Continue in this way. In the penultimate step, keep the closest prime number not exceeding x in the remaining sequence and eliminate all its multiples. Thus, the remaining sequence is all the prime numbers not exceeding x. The above approach is based on the fact that if a is not a prime number, then a must have a factor not exceeding .
The Sieve of Eratosthenes can be used to compile a prime number table more conveniently. If we encounter a not-too-large positive integer a (such as not exceeding 10,000) and don't have a prime number table available, how can we quickly determine whether it is a prime number? In fact, we can simply try dividing a by all primes not exceeding .