What is the best algorithm for checking if a numbe

Question

Just an example of what I am looking for: I could represent every odd number with a bit e.g. for the given range of numbers (1, 10], starts at 3:

1110

The following dictionary can be squeezed more right? I could eleminate multiples of five with some work, but numbers that end with 1, 3, 7 or 9 must be there in the array of bits. Hope this would clarify what I want.

I am looking for the best algorithm, to check if a number is prime i.e. a boolean function:

bool isprime(number);

I would like to know the best algorithm to implement this functionality. Naturally, there would be a data structure I could query. I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a constant.

Answer 1

Similar idea to the AKS algorithm which has been mentioned

public static boolean isPrime(int n) {

    if(n == 2 || n == 3) return true;
    if((n & 1 ) == 0 || n % 3 == 0) return false;
    int limit = (int)Math.sqrt(n) + 1;
    for(int i = 5, w = 2; i <= limit; i += w, w = 6 - w) {
        if(n % i == 0) return false;
        numChecks++;
    }
    return true;
}

Answer 2

I think one of the fastest is my method that I made.

void prime(long long int number) {
    // Establishing Variables
    long long int i = 5;
    int w = 2;
    const long long int lim = sqrt(number);

    // Gets 2 and 3 out of the way
    if (number == 1) { cout << number << " is hard to classify. \n";  return; }
    if (number == 2) { cout << number << " is Prime. \n";  return; }
    if (number == 3) { cout << number << " is Prime. \n";  return; }

    // Tests Odd Ball Factors
    if (number % 2 == 0) { cout << number << " is not Prime. \n";  return; }
    if (number % 3 == 0) { cout << number << " is not Prime. \n";  return; }

    while (i <= lim) {
        if (number % i == 0) { cout << number << " is not Prime. \n";  return; }
        // Tests Number
        i = i + w; // Increments number
        w = 6 - i; // We already tested 2 and 3
        // So this removes testing multepules of this
    }
    cout << number << " is Prime. \n"; return;
}

Answer 3

Way too late to the party, but hope this helps. This is relevant if you are looking for big primes:

To test large odd numbers you need to use the Fermat-test and/or Miller-Rabin test.

These tests use modular exponentiation which is quite expensive, for n bits exponentiation you need at least n big int multiplication and n big int divison. Which means the complexity of modular exponentiation is O(n³).

So before using the big guns, you need to do quite a few trial divisions. But don't do it naively, there is a way to do them fast. First multiply as many primes together as many fits into a the words you use for the big integers. If you use 32 bit words, multiply 3*5*7*11*13*17*19*23*29=3234846615 and compute the greatest common divisor with the number you test using the Euclidean algorithm. After the first step the number is reduced below the word size and continue the algorithm without performing complete big integer divisions. If the GCD != 1, that means one of the primes you multiplied together divides the number, so you have a proof it's not prime. Then continue with 31*37*41*43*47 = 95041567, and so on.

Once you tested several hundred (or thousand) primes this way, you can do 40 rounds of Miller-Rabin test to confirm the number is prime, after 40 rounds you can be certain the number is prime there is only 2^-80 chance it's not (it's more likely your hardware malfunctions...).

Answer 4

Most of previous answers are correct but here is one more way to test to see a number is prime number. As refresher, prime numbers are whole number greater than 1 whose only factors are 1 and itself.(source)

Solution:

Typically you can build a loop and start testing your number to see if it's divisible by 1,2,3 ...up to the number you are testing ...etc but to reduce the time to check, you can divide your number by half of the value of your number because a number cannot be exactly divisible by anything above half of it's value. Example if you want to see 100 is a prime number you can loop through up to 50.

Actual code:

def find_prime(number):
    if(number ==1):
        return False
    # we are dividiing and rounding and then adding the remainder to increment !
    # to cover not fully divisible value to go up forexample 23 becomes 11
    stop=number//2+number%2
    #loop through up to the half of the values
    for item in range(2,stop):
        if number%item==0:
           return False
        print(number)
    return True


if(find_prime(3)):
    print("it's a prime number !!")
else:
    print("it's not a prime")  

Answer 5

With help of Java-8 streams and lambdas, it can be implemented like this in just few lines:

public static boolean isPrime(int candidate){
        int candidateRoot = (int) Math.sqrt( (double) candidate);
        return IntStream.range(2,candidateRoot)
                .boxed().noneMatch(x -> candidate % x == 0);
    }

Performance should be close to O(sqrt(N)). Maybe someone find it useful.

Answer 6

I have got a prime function which works until (2^61)-1 Here:

from math import sqrt
def isprime(num): num > 1 and return all(num % x for x in range(2, int(sqrt(num)+1)))

Explanation:

The all() function can be redefined to this:

def all(variables):
    for element in variables:
        if not element: return False
    return True

The all() function just goes through a series of bools / numbers and returns False if it sees 0 or False.

The sqrt() function is just doing the square root of a number.

For example:

>>> from math import sqrt
>>> sqrt(9)
>>> 3
>>> sqrt(100)
>>> 10

The num % x part returns the remainder of num / x.

Finally, range(2, int(sqrt(num))) means that it will create a list that starts at 2 and ends at int(sqrt(num)+1)

For more information about range, have a look at this website!

The num > 1 part is just checking if the variable num is larger than 1, becuase 1 and 0 are not considered prime numbers.

I hope this helped :)