Could i <= n / i be wrong in some cases because of division?

Revision en1, by Destopia, 2022-04-08 23:55:08

Let's say I want to check whether an integer is prime or not.

Implementation $$$1$$$:

bool is_prime1(long long n) {
    if (n < 2)
        return false;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Implementation $$$2$$$:

bool is_prime2(long long n) {
    if (n < 2)
        return false;
    for (long long i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Which implementation is better?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Destopia 2022-04-08 23:55:08 668 Initial revision (published)