We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Time Complexity: Primality
  2. Discussions

Time Complexity: Primality

  • urossevkusic
     + 0 comments

    Actually, there's an O(logN) solution. Here's my code, it works for all numbers from 1 to 2^64. It's based on Miller-Rabin test, with a proven array of bases from this site.

    unsigned long long fast_mod_pow(unsigned long long x, unsigned long long y, unsigned long long z) {
    unsigned long long r = 1;
    while(y) {
        if(y & 1)
            r = (unsigned __int128)r * x % z;
        y >>= 1;
        x = (unsigned __int128) x * x % z;
    }
    return r;
}

std::array<int, 7> bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};

bool miller_rabin(unsigned long long a, unsigned long long t, unsigned long long h, unsigned long long n) {
    
    unsigned long long b = fast_mod_pow(a, t, n);
    if(b < 2) return true;
    
    for(unsigned long long i = 0; i < h; ++i) {
        if(b == 1) return false;
        if(b == n - 1) return true;
        b = fast_mod_pow(b, 2, n);
    }
    return false;
}

bool is_prime(unsigned long long n) {
    if(n < 4) return n > 1;
    if(!(n & 1)) return false;
    unsigned long long t = n - 1, h = 0;
    while(!(t & 1)) {
        t >>= 1;
        ++h;
    }
    
    for(unsigned long long a : bases) {
        if(!miller_rabin(a, t, h, n)) return false;
    }
    
    return true;
}

string primality(int n) {   
    return is_prime(n)? "Prime" : "Not prime";
}