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?
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)
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.
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)
Which Technique is good to counter problems with the constraint Kataude_no_kaizoku mentioned?
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 ;)
《PRIMES is in P》 Do you know AKS or Miller-Rabin?
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 :)
FWIW
*operator is faster than/operator, so first implementation has lower constantNo! Calculating
n / iis free, because the loop body is already calculatingn % 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.