Which approach best describes generating the first X prime numbers by testing each candidate for primality?

• A. Testing each candidate for primality by dividing only by 2
• B. Testing each candidate for primality by dividing by numbers up to the square root of the candidate
• C. Using a fixed precomputed list of primes
• D. Skipping primality checks and returning the first X odd numbers

Answer: (B)

When assessing whether a candidate number is prime, you only need to check divisibility up to its square root. The reason is that if a number n is composite, it can be written as a product a × b with both a and b greater than 1. In such a case, the smaller factor a cannot exceed sqrt(n); otherwise the product would exceed n. So if no divisor in the range from 2 up to floor(sqrt(n)) divides n, there is no pair of factors, and n must be prime. This makes the primality test efficient: you avoid checking every number up to n−1 and instead limit the work to numbers up to sqrt(n).

The alternative of dividing only by 2 would miss many composites (for example, 9 is divisible by 3, not by 2). Relying on a fixed precomputed list of primes can fail for larger numbers beyond the list’s range, and skipping primality checks would just yield a sequence of numbers that includes many composites. The square-root bound is the clean, correct rule for determining primality in this context.