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

Have you ever used an improved primality test?
Автор 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;
}
  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
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

→ Ответить
»
4 года назад, # |
← Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

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;

}

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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;
}
    → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

  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.

→ Ответить