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

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

Implementation 11:

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 22:

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?

• 30 hours ago, # ^ |

  It doesn't matter at all, they are basically the same code. And as for big constraints, how exactly would the Sieve of Eratosthenes help? remember, it's O(nlogn) for time and O(n) for space. (You can speed up the primality test by a tiny bit, by looping over primes smaller than the square root, but that only makes it O(sqrt(n)/log(n)) which is really redundant)

  • 19 hours ago, # ^ |

    Which Technique is good to counter problems with the constraint marooonik mentioned?

    • 17 hours ago, # ^ |

      Pretty sure there isn't an algorithm for primality testing faster than O(sqrt(n)). The Sieve of Eratosthenes can help with stuff like fast primality testing or prime factorization of many numbers in a reasonable range (like 1e6) (O(nlogn) for creation and O(1) for checking primality and O(sum of powers in prime factorization which is worst case logn) for prime factorization)

      Sorry for the layered brackets ;)

      • 16 hours ago, # ^ |

        《PRIMES is in P》 Do you know AKS or Miller-Rabin?

        • 16 hours ago, # ^ |

          According to wikipedia AKS is not used in practice due to its big constant factor.

          Miler-Rabin however looks good, thanks for letting me know, will look into that :)

• 10 hours ago, # ^ |

  No! Calculating n / i is free, because the loop body is already calculating n % i, and a decent compiler is smart enough to share them. They both take exactly the same amount of time because they are limited by the poor throughput of the 64-bit div/mod CPU instruction.