## "Fossies" - the Fresh Open Source Software Archive

skipping to change at line 55 skipping to change at line 55
bool IsPrime(int n) { bool IsPrime(int n) {
// Trivial case 1: small numbers // Trivial case 1: small numbers
if (n <= 1) return false; if (n <= 1) return false;
// Trivial case 2: even numbers // Trivial case 2: even numbers
if (n % 2 == 0) return n == 2; if (n % 2 == 0) return n == 2;
// Now, we have that n is odd and n >= 3. // Now, we have that n is odd and n >= 3.
// Try to divide n by every odd number i, starting from 3 // Try to divide n by every odd number i, starting from 3
for (int i = 3;; i += 2) { for (int i = 3;; i += 2) {
// We only have to try i up to the square root of n // We only have to try i up to the square root of n
if (i > ni) break; if (i > n / i) break;
// Now, we have i <= n/i < n. // Now, we have i <= n/i < n.
// If n is divisible by i, n is not prime. // If n is divisible by i, n is not prime.
if (n % i == 0) return false; if (n % i == 0) return false;
} }
// n has no integer factor in the range (1, n), and thus is prime. // n has no integer factor in the range (1, n), and thus is prime.
return true; return true;
} }
End of changes. 2 change blocks.
2 lines changed or deleted 2 lines changed or added