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

Sort by

recency

|

202 Discussions

|

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

  • harrisduque
     + 0 comments

    Python solution:

    def primality(n):
    if n < 2:
        return "Not prime"
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return "Not prime"
    return "Prime"

  • concealedgloomy
     + 0 comments

    My solution Java 7 (I haven't read the editorial yet)

    public static String primality(int n) {
        
        if (n < 2) {
            return "Not prime";
        }
        
        for (int i = 2 ; i < n ; i++) {
            if (n % i == 0) {
                return "Not prime";
            }   
        }
        
        return "Prime";
        
}

  • aquajim03
     + 0 comments
    string primality(int n) {
    bool flag = true;
    if(n == 1){
        flag = false;
    }
    for(int i = 2; i <= sqrt(n); ++i){
        if(n % i == 0){
            flag = false;
        }
    }
    return flag ? "Prime" : "Not prime";
}

  • ramanani239
     + 0 comments
    public static String primality(int n) {
        if(n==1)
            return "Not prime";
    // Write your code here
    int count =0;
    for(int i=1;i<=Math.sqrt(n);i++){
        if(n%i==0){
            count++;
        }
    }
    if(count==1){
        return "Prime";
    }else{
        return "Not prime";
    }
    }