理解教材中的Ruby质数判定程序：关于内层循环的疑问

Great question—let's break this down into two key areas: whether the prime results stay accurate, and how the program's speed changes.

First, let's recap the original logic: the inner loop checks if i is divisible by any number j starting at 2, up to i/2. If any divisor is found, prime_flag gets flipped to false, meaning i isn't a prime.

1. Impact on Prime Check Correctness #

The correctness depends entirely on whether your adjusted condition still checks enough divisors to rule out composites:

• Tightening to j <= Math.sqrt(i): This is 100% correct. Here's why: if a number i has a factor larger than its square root, the corresponding pair factor must be smaller than the square root. For example, 25's square root is 5—its factors are 5×5, and any larger factor (like 25 itself) would pair with 1, which we don't check anyway. So checking up to sqrt(i) covers all possible divisors needed to confirm primality. The results will match the original program perfectly.
• Widening to j < i: This is also correct, but redundant. Checking every number from 2 up to i-1 will definitely catch all divisors, but you're doing way more work than necessary (e.g., checking 9 for divisibility by 8,7,6 when 3 already tells you it's composite). The prime results will still be accurate, though.
• Making the condition too narrow (e.g., j <= i/3 or j <= Math.sqrt(i) - 1): This breaks correctness. For example, if you set j <= 4 for i=25, the loop will check 2,3,4—none divide 25 evenly—so the program will incorrectly mark 25 as prime. You're skipping the critical divisor (5) that would reveal it's a composite.

2. Impact on Runtime Performance #

Performance is directly tied to how many iterations the inner loop runs:

• Fewer iterations = faster performance: Switching from j <= i/2 to j <= Math.sqrt(i) drastically reduces loop runs. For i=100, the original loop runs 49 times (from 2 to 50), while the sqrt version runs only 9 times (from 2 to 10). The larger i gets, the bigger this performance gap becomes—for i=10000, i/2 is 5000, but sqrt(i) is 100. That's a huge difference in execution time.
• More iterations = slower performance: Using j < i makes the program run much slower, especially for large i. For i=100, you're looping 98 times instead of 49—double the work. For very large primes, this becomes a massive waste of resources.
• Original condition (j <= i/2): This is a middle ground—it's better than checking all numbers up to i-1, but still far less efficient than checking up to sqrt(i).

One quick win for performance, regardless of the condition: uncomment the break statement in the inner loop! Once you find a divisor, there's no need to keep checking other numbers—breaking out of the loop immediately cuts down on unnecessary iterations.

内容的提问来源于stack exchange，提问作者Red is Purple