Qualified's blog

Have you ever used an improved primality test?
By Qualified, 4 years ago, In English

Have you ever used an improved primality test such as Miller-Rabin algorithm? Also can you guys/gals think of any optimizations to this primality test?

bool isprime(ll n) {
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}
  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it
Have you ever used an improved primality test such as Miller-Rabin algorithm?

Nope,never.

Also in your algo, Include a condition for n=1. I have received several WAs in the past for forgetting 1 is not a prime.

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

For low constrain this algorithm is enough I think. Bt for high range seive of eratosthenes is better.

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

    What would be the time complexity of the Sieve of Eratosthenes and how would you implement it?

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

If you’re a Java boy, there is BigInteger.isProbablePrime(). Would recommend for any reasonable problem where you just need to check one prime if there are no other constraints to abuse

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +8 Vote: I do not like it

Yes a bit of optimization that I use as a result of the fact that all prime numbers greater than 3 are always of the form 6k+1 or 6k+5.

bool isPrime ( int n)

{

if (n <= 1) return false; 
if (n <= 3) return true; 

if (n%2 == 0 || n%3 == 0) return false; 

for (int i=5; i*i<=n; i=i+6) 
    if (n%i == 0 || n%(i+2) == 0) 
    return false; 

return true;

}

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

    Change i * i <= n -> i <= lim where lim is precalculated as sqrtn will optimize a bit and may avoid overflow in some other similar functions

    bool isPrime(int n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (!(n & 1))   return false; /// n % 2 == 0
    if (n % 3 == 0) return false;

    int lim = sqrt(n);
    for (int i = 5; i <= lim; i += 6)
        if (n % i == 0 || n % (i + 2) == 0)
             return false;

    return true;
}
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

  1. Sure.

  2. Currently it doesn't work for 64-bit integers as the signature would suggest. Either downshift ll n to int n or account for integer overflow. To do the latter, for example, transform i * i into i * 1LL * i.

→ Reply