Have you ever used an improved primality test?

Блог пользователя Qualified

Автор Qualified, 4 года назад, По-английски

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

#primality_test, #optimization

-6

Qualified
4 года назад
10

Комментарии (8)

Показать архивные | Написать комментарий?

pritishn

4 года назад, # |

← Rev. 2 →

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.

→ Ответить

sqL_slammer

4 года назад, # |

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

→ Ответить

Qualified

4 года назад, # ^ |

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

→ Ответить

SecondThread

4 года назад, # |

+21

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

→ Ответить

Qualified

4 года назад, # ^ |

Me no Java boy, Me is C++ boy.

→ Ответить

mallick630

4 года назад, # |

← Rev. 5 →

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;

}

→ Ответить

SPyofgame

4 года назад, # ^ |

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

→ Ответить

Gassa

4 года назад, # |

Sure.
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.

→ Ответить