Destopia's blog

Could i <= n / i be wrong in some cases because of division?
By Destopia, history, 3 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I mean, they look pretty similar to me, and they are both correct. (the second implementation won't be wrong because the only case it could have problems with is when n is a square, and the <= will take care of that)

→ Reply
»
3 years ago, # |
  Vote: I like it -16 Vote: I do not like it

I checked the following implementations on multiple test cases but I couldn't find any sort of TLEs in my code. Maybe it doesn't matter too much whether you use the first implementation or the second implementation. I think both of them will work fine. Obviously these are brute-force approaches, you can't use them in problems with very big constraints like 2e18 or so. You'll have to use techniques like Sieve of Eratosthenes to counter such problems.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ;)

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

FWIW * operator is faster than / operator, so first implementation has lower constant

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply