How to create the most compact mapping n → isprime(n) up to a limit N?

I compared the efficiency of the most popular suggestions to determine if a number is prime. I used python 3.6 on ubuntu 17.10; I tested with numbers up to 100.000 (you can test with bigger numbers using my code below).

This first plot compares the functions (which are explained further down in my answer), showing that the last functions do not grow as fast as the first one when increasing the numbers.

And in the second plot we can see that in case of prime numbers the time grows steadily, but non-prime numbers do not grow so fast in time (because most of them can be eliminated early on).

Here are the functions I used:

1. this answer and this answer suggested a construct using all():

   def is_prime_1(n):
       return n > 1 and all(n % i for i in range(2, int(math.sqrt(n)) + 1))
   

2. This answer used some kind of while loop:

   def is_prime_2(n):
       if n <= 1:
           return False
       if n == 2:
           return True
       if n == 3:
           return True
       if n % 2 == 0:
           return False
       if n % 3 == 0:
           return False
   
       i = 5
       w = 2
       while i * i <= n:
           if n % i == 0:
               return False
           i += w
           w = 6 - w
   
       return True
   

3. This answer included a version with a for loop:

   def is_prime_3(n):
       if n <= 1:
           return False
   
       if n % 2 == 0 and n > 2:
           return False
   
       for i in range(3, int(math.sqrt(n)) + 1, 2):
           if n % i == 0:
               return False
   
       return True
   

4. And I mixed a few ideas from the other answers into a new one:

   def is_prime_4(n):
       if n <= 1:          # negative numbers, 0 or 1
           return False
       if n <= 3:          # 2 and 3
           return True
       if n % 2 == 0 or n % 3 == 0:
           return False
   
       for i in range(5, int(math.sqrt(n)) + 1, 2):
           if n % i == 0:
               return False
   
       return True
   

Here is my script to compare the variants:

import math
import pandas as pd
import seaborn as sns
import time
from matplotlib import pyplot as plt


def is_prime_1(n):
    ...
def is_prime_2(n):
    ...
def is_prime_3(n):
    ...
def is_prime_4(n):
    ...

default_func_list = (is_prime_1, is_prime_2, is_prime_3, is_prime_4)

def assert_equal_results(func_list=default_func_list, n):
    for i in range(-2, n):
        r_list = [f(i) for f in func_list]
        if not all(r == r_list[0] for r in r_list):
            print(i, r_list)
            raise ValueError
    print('all functions return the same results for integers up to {}'.format(n))

def compare_functions(func_list=default_func_list, n):
    result_list = []
    n_measurements = 3

    for f in func_list:
        for i in range(1, n + 1):
            ret_list = []
            t_sum = 0
            for _ in range(n_measurements):
                t_start = time.perf_counter()
                is_prime = f(i)
                t_end = time.perf_counter()

                ret_list.append(is_prime)
                t_sum += (t_end - t_start)

            is_prime = ret_list[0]
            assert all(ret == is_prime for ret in ret_list)
            result_list.append((f.__name__, i, is_prime, t_sum / n_measurements))

    df = pd.DataFrame(
        data=result_list,
        columns=['f', 'number', 'is_prime', 't_seconds'])
    df['t_micro_seconds'] = df['t_seconds'].map(lambda x: round(x * 10**6, 2))
    print('df.shape:', df.shape)

    print()
    print('', '-' * 41)
    print('| {:11s} | {:11s} | {:11s} |'.format(
        'is_prime', 'count', 'percent'))
    df_sub1 = df[df['f'] == 'is_prime_1']
    print('| {:11s} | {:11,d} | {:9.1f} % |'.format(
        'all', df_sub1.shape[0], 100))
    for (is_prime, count) in df_sub1['is_prime'].value_counts().iteritems():
        print('| {:11s} | {:11,d} | {:9.1f} % |'.format(
            str(is_prime), count, count * 100 / df_sub1.shape[0]))
    print('', '-' * 41)

    print()
    print('', '-' * 69)
    print('| {:11s} | {:11s} | {:11s} | {:11s} | {:11s} |'.format(
        'f', 'is_prime', 't min (us)', 't mean (us)', 't max (us)'))
    for f, df_sub1 in df.groupby(['f', ]):
        col = df_sub1['t_micro_seconds']
        print('|{0}|{0}|{0}|{0}|{0}|'.format('-' * 13))
        print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format(
            f, 'all', col.min(), col.mean(), col.max()))
        for is_prime, df_sub2 in df_sub1.groupby(['is_prime', ]):
            col = df_sub2['t_micro_seconds']
            print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format(
                f, str(is_prime), col.min(), col.mean(), col.max()))
    print('', '-' * 69)

    return df

Running the function compare_functions(n=10**5) (numbers up to 100.000) I get this output:

df.shape: (400000, 5)

 -----------------------------------------
| is_prime    | count       | percent     |
| all         |     100,000 |     100.0 % |
| False       |      90,408 |      90.4 % |
| True        |       9,592 |       9.6 % |
 -----------------------------------------

 ---------------------------------------------------------------------
| f           | is_prime    | t min (us)  | t mean (us) | t max (us)  |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_1  | all         |        0.57 |        2.50 |      154.35 |
| is_prime_1  | False       |        0.57 |        1.52 |      154.35 |
| is_prime_1  | True        |        0.89 |       11.66 |       55.54 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_2  | all         |        0.24 |        1.14 |      304.82 |
| is_prime_2  | False       |        0.24 |        0.56 |      304.82 |
| is_prime_2  | True        |        0.25 |        6.67 |       48.49 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_3  | all         |        0.20 |        0.95 |       50.99 |
| is_prime_3  | False       |        0.20 |        0.60 |       40.62 |
| is_prime_3  | True        |        0.58 |        4.22 |       50.99 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_4  | all         |        0.20 |        0.89 |       20.09 |
| is_prime_4  | False       |        0.21 |        0.53 |       14.63 |
| is_prime_4  | True        |        0.20 |        4.27 |       20.09 |
 ---------------------------------------------------------------------

Then, running the function compare_functions(n=10**6) (numbers up to 1.000.000) I get this output:

df.shape: (4000000, 5)

 -----------------------------------------
| is_prime    | count       | percent     |
| all         |   1,000,000 |     100.0 % |
| False       |     921,502 |      92.2 % |
| True        |      78,498 |       7.8 % |
 -----------------------------------------

 ---------------------------------------------------------------------
| f           | is_prime    | t min (us)  | t mean (us) | t max (us)  |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_1  | all         |        0.51 |        5.39 |     1414.87 |
| is_prime_1  | False       |        0.51 |        2.19 |      413.42 |
| is_prime_1  | True        |        0.87 |       42.98 |     1414.87 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_2  | all         |        0.24 |        2.65 |      612.69 |
| is_prime_2  | False       |        0.24 |        0.89 |      322.81 |
| is_prime_2  | True        |        0.24 |       23.27 |      612.69 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_3  | all         |        0.20 |        1.93 |       67.40 |
| is_prime_3  | False       |        0.20 |        0.82 |       61.39 |
| is_prime_3  | True        |        0.59 |       14.97 |       67.40 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_4  | all         |        0.18 |        1.88 |      332.13 |
| is_prime_4  | False       |        0.20 |        0.74 |      311.94 |
| is_prime_4  | True        |        0.18 |       15.23 |      332.13 |
 ---------------------------------------------------------------------

I used the following script to plot the results:

def plot_1(func_list=default_func_list, n):
    df_orig = compare_functions(func_list=func_list, n=n)
    df_filtered = df_orig[df_orig['t_micro_seconds'] <= 20]
    sns.lmplot(
        data=df_filtered, x='number', y='t_micro_seconds',
        col='f',
        # row='is_prime',
        markers='.',
        ci=None)

    plt.ticklabel_format(style='sci', axis='x', scilimits=(3, 3))
    plt.show()

One can use sympy.

import sympy

sympy.ntheory.primetest.isprime(33393939393929292929292911111111)

True

From sympy docs. The first step is looking for trivial factors, which if found enables a quick return. Next, if the sieve is large enough, use bisection search on the sieve. For small numbers, a set of deterministic Miller-Rabin tests are performed with bases that are known to have no counterexamples in their range. Finally if the number is larger than 2^64, a strong BPSW test is performed. While this is a probable prime test and we believe counterexamples exist, there are no known counterexamples

For large numbers you cannot simply naively check whether the candidate number N is divisible by none of the numbers less than sqrt(N). There are much more scalable tests available, such as the Miller-Rabin primality test. Below you have implementation in python:

def is_prime(x):
    """Fast implementation fo Miller-Rabin primality test, guaranteed to be correct."""
    import math
    def get_sd(x):
        """Returns (s: int, d: int) for which x = d*2^s """
        if not x: return 0, 0
        s = 0
        while 1:
            if x % 2 == 0:
                x /= 2
                s += 1
            else:
                return s, x
    if x <= 2:
        return x == 2
    # x - 1 = d*2^s
    s, d = get_sd(x - 1)
    if not s:
        return False  # divisible by 2!
    log2x = int(math.log(x) / math.log(2)) + 1
    # As long as Riemann hypothesis holds true, it is impossible
    # that all the numbers below this threshold are strong liars.
    # Hence the number is guaranteed to be a prime if no contradiction is found.
    threshold = min(x, 2*log2x*log2x+1)
    for a in range(2, threshold):
        # From Fermat's little theorem if x is a prime then a^(x-1) % x == 1
        # Hence the below must hold true if x is indeed a prime:
        if pow(a, d, x) != 1:
            for r in range(0, s):
                if -pow(a, d*2**r, x) % x == 1:
                    break
            else:
                # Contradicts Fermat's little theorem, hence not a prime.
                return False
    # No contradiction found, hence x must be a prime.
    return True

You can use it to find huge prime numbers:

x = 10000000000000000000000000000000000000000000000000000000000000000000000000000
for e in range(1000):
    if is_prime(x + e):
        print('%d is a prime!' % (x + e))
        break

# 10000000000000000000000000000000000000000000000000000000000000000000000000133 is a prime!

If you are testing random integers probably you want to first test whether the candidate number is divisible by any of the primes smaller than, say 1000, before you call Miller-Rabin. This will help you filter out obvious non-primes such as 10444344345.

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

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 :)

In Python:

def is_prime(n):
    return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1))

A more direct conversion from mathematical formalism to Python would use all(n % p != 0... ), but that requires strict evaluation of all values of p. The not any version can terminate early if a True value is found.

best algorithm for Primes number javascript

 function isPrime(num) {
      if (num <= 1) return false;
      else if (num <= 3) return true;
      else if (num % 2 == 0 || num % 3 == 0) return false;
      var i = 5;
      while (i * i <= num) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
        i += 6;
      }
      return true
    }

A prime number is any number that is only divisible by 1 and itself. All other numbers are called composite.

The simplest way, of finding a prime number, is to check if the input number is a composite number:

    function isPrime(number) {
        // Check if a number is composite
        for (let i = 2; i < number; i++) {
            if (number % i === 0) {
                return false;
            }
        }
        // Return true for prime numbers
        return true;
    }

The program has to divide the value of number by all the whole numbers from 1 and up to the its value. If this number can be divided evenly not only by one and itself it is a composite number.

The initial value of the variable i has to be 2 because both prime and composite numbers can be evenly divided by 1.

    for (let i = 2; i < number; i++)

Then i is less than number for the same reason. Both prime and composite numbers can be evenly divided by themselves. Therefore there is no reason to check it.

Then we check whether the variable can be divided evenly by using the remainder operator.

    if (number % i === 0) {
        return false;
    }

If the remainder is zero it means that number can be divided evenly, hence being a composite number and returning false.

If the entered number didn't meet the condition, it means it's a prime number and the function returns true.

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")  

We can use java streams to implement this in O(sqrt(n)); Consider that noneMatch is a shortCircuiting method that stops the operation when finds it unnecessary for determining the result:

Scanner in = new Scanner(System.in);
int n = in.nextInt();
System.out.println(n == 2 ? "Prime" : IntStream.rangeClosed(2, ((int)(Math.sqrt(n)) + 1)).noneMatch(a -> n % a == 0) ? "Prime" : "Not Prime");

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.

Let me suggest you the perfect solution for 64 bit integers. Sorry to use C#. You have not already specified it as python in your first post. I hope you can find a simple modPow function and analyze it easily.

public static bool IsPrime(ulong number)
{
    return number == 2 
        ? true 
        : (BigInterger.ModPow(2, number, number) == 2 
            ? ((number & 1) != 0 && BinarySearchInA001567(number) == false) 
            : false)
}

public static bool BinarySearchInA001567(ulong number)
{
    // Is number in list?
    // todo: Binary Search in A001567 (https://oeis.org/A001567) below 2 ^ 64
    // Only 2.35 Gigabytes as a text file http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html
}

bool isPrime(int n) {
if(n <= 3)
    return (n > 1)==0? false: true;
else if(n%2 == 0 || n%3 == 0)
    return false;

int i = 5;

while(i * i <= n){
    if(n%i == 0 || (n%(i+2) == 0))
        return false;
    i = i + 6;
}

return true;
}

For any number, the minimum iterations to check if the number is prime or not can be from 2 to square root of the number. To reduce the iterations, even more, we can check if the number is divisible by 2 or 3 as maximum numbers can be eliminated by checking if the number is divisible by 2 or 3. Further any prime number greater than 3 can be expressed as 6k+1 or 6k-1. So the iteration can go from 6k+1 to the square root of the number.

### is_prime(number) = 
### if number % p1 !=0 for all p1(prime numbers)  < (sqrt(number) + 1), 
### filter numbers that are not prime from divisors

import math
def check_prime(N, prime_numbers_found = [2]):
    if N == 2:
        return True
    if int(math.sqrt(N)) + 1 > prime_numbers_found[-1]:
        divisor_range = prime_numbers_found + list(range(prime_numbers_found[-1] + 1, int(math.sqrt(N)) + 1+ 1))
    else:
        divisor_range = prime_numbers_found
    #print(divisor_range, N)

    for number in divisor_range:
        if number not in prime_numbers_found:
             if check_prime(number, prime_numbers_found):
                prime_numbers_found.append(number)
                if N % number == 0:
                    return False
        else:
            if N % number == 0:
                return False

    return True

BEST SOLUTION

I an unsure if I understand the concept of Time complexity: O(sqrt(n)) and Space complexity: O(1) in this context but the function prime(n) is probably the fastest way (least iterations) to calculate if a number is prime number of any size.

This probably is the BEST solution in the internet as of today 11th March 2022. Feedback and usage is welcome.

This same code can be applied in any languages like C, C++, Go Lang, Java, .NET, Python, Rust, etc with the same logic and have performance benefits. It is pretty fast. I have not seen this implemented before and has been indigenously done.

If you are looking at the speed and performance here is the """BEST""" hopeful solution I can give:

Max iterations 16666 for n == 100000 instead of 100000 of conventional way

The codes can also be found here: https://github.com/ganeshkbhat/fastprimecalculations

If you use it for your project please spend 2 minutes of your time crediting me by letting me know by either sending me an email, or logging an Github issue with subject heading [User], or star my Github project. But let me know here https://github.com/ganeshkbhat/fastprimecalculations. I would love to know the fans and users of the code logic

def prime(n):
    if ((n == 2 or n == 3 or n == 5 or n == 7)):
        return True
    
    if (n == 1 or ((n > 7) and (n % 5 == 0 or n % 7 == 0 or n % 2 == 0 or n % 3 == 0))):
        return False
    
    if ( type((n - 1) / 6) == int or type((n + 1) / 6) == int):
        for i in range(1, n):
            factorsix = (i * 6)
            five = n / (5 + factorsix)
            seven = n / (7 + factorsix)
            if ( ((five > 1) and type(five) == int) or ((seven > 1) and type(five) == int) ):
                return False;
            
            if (factorsix > n):
                break;
        return True
    return False

Here is an analysis of all the ways of calculation:

Conventional way of checking for prime:

def isPrimeConventionalWay(n):
    count = 0
    if (n <= 1):
        return False;
    # Check from 2 to n-1
    # Max iterations 99998 for n == 100000 
    for i in range(2,n):
        # Counting Iterations
        count += 1
        if (n % i == 0):
            print("count: Prime Conventional way", count)
            return False;
    print("count: Prime Conventional way", count)
    return True;

SQUAREROOT way of checking for prime:

def isPrimeSquarerootWay(num):
    count = 0
    # if not is_number num return False
    if (num < 2):
        print("count: Prime Squareroot way", count)
        return False
    
    s = math.sqrt(num)
    for  i in range(2, num):
        # Counting Iterations
        count += 1
        if (num % i == 0):
            print("count: Prime Squareroot way", count)
            return False
    print("count: Prime Squareroot way", count)
    return True

OTHER WAYS:

def isprimeAKSWay(n):
    """Returns True if n is prime."""
    count = 0
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        count += 1
        if n % i == 0:
            print("count: Prime AKS - Mersenne primes - Fermat's little theorem or whatever way", count)
            return False

        i += w
        w = 6 - w
    print("count: Prime AKS - Mersenne primes - Fermat's little theorem or whatever way", count)
    return True

SUGGESTED way of checking for prime:

def prime(n):
    count = 0
    if ((n == 2 or n == 3 or n == 5 or n == 7)):
        print("count: Prime Unconventional way", count)
        return True
    
    if (n == 1 or ((n > 7) and (n % 5 == 0 or n % 7 == 0 or n % 2 == 0 or n % 3 == 0))):
        print("count: Prime Unconventional way", count)
        return False
    
    if (((n - 1) / 6).is_integer()) or (((n + 1) / 6).is_integer()):
        for i in range(1, n):
            # Counting Iterations
            count += 1
            five = 5 + (i * 6)
            seven = 7 + (i * 6)
            if ((((n / five) > 1) and (n / five).is_integer()) or (((n / seven) > 1) and ((n / seven).is_integer()))):
                print("count: Prime Unconventional way", count)
                return False;
            
            if ((i * 6) > n):
                # Max iterations 16666 for n == 100000 instead of 100000
                break;
            
        print("count: Prime Unconventional way", count)
        return True
    
    print("count: Prime Unconventional way", count)
    return False

Tests to compare with the traditional way of checking for prime numbers.

def test_primecalculations():
    count = 0
    iterations = 100000
    arr = []
    for i in range(1, iterations):
        traditional = isPrimeConventionalWay(i)
        newer = prime(i)
        if (traditional == newer):
            count = count + 1
        else:
            arr.push([traditional, newer, i])
    print("[count, iterations, arr] list: ", count, iterations, arr)
    if (count == iterations):
        return True
    return False


# print("Tests Passed: ", test_primecalculations())
    

You will see the results of count of number of iterations as below for check of prime number: 100007:

print("Is Prime 100007: ", isPrimeConventionalWay(100007))
print("Is Prime 100007: ", isPrimeSquarerootWay(100007))
print("Is Prime 100007: ", prime(100007))
print("Is Prime 100007: ", isprimeAKSWay(100007))

count: Prime Conventional way 96
Is Prime 100007:  False
count: Prime Squareroot way 96
Is Prime 100007:  False
count: Prime Unconventional way 15
Is Prime 100007:  False
count: Prime AKS - Mersenne primes - Fermat's little theorem or whatever way 32
Is Prime 100007:  False

Here are some performance tests and results below:

import time
isPrimeConventionalWayArr = []
isPrimeSquarerootWayArr = []
primeArr = []
isprimeAKSWayArr = []


def tests_performance_isPrimeConventionalWayArr():
    global isPrimeConventionalWayArr
    for i in range(1, 1000000):
        start = time.perf_counter_ns()
        isPrimeConventionalWay(30000239)
        end = time.perf_counter_ns()
        isPrimeConventionalWayArr.append(end - start)
tests_performance_isPrimeConventionalWayArr()


def tests_performance_isPrimeSquarerootWayArr():
    global isPrimeSquarerootWayArr
    for i in range(1, 1000000):
        start = time.perf_counter_ns()
        isPrimeSquarerootWay(30000239)
        end = time.perf_counter_ns()
        isPrimeSquarerootWayArr.append(end - start)
tests_performance_isPrimeSquarerootWayArr()


def tests_performance_primeArr():
    global primeArr
    for i in range(1, 1000000):
        start = time.perf_counter_ns()
        prime(30000239)
        end = time.perf_counter_ns()
        primeArr.append(end - start)
tests_performance_primeArr()

def tests_performance_isprimeAKSWayArr():
    global isprimeAKSWayArr
    for i in range(1, 1000000):
        start = time.perf_counter_ns()
        isprimeAKSWay(30000239)
        end = time.perf_counter_ns()
        isprimeAKSWayArr.append(end - start)
tests_performance_isprimeAKSWayArr()  


print("isPrimeConventionalWayArr: ", sum(isPrimeConventionalWayArr)/len(isPrimeConventionalWayArr))
print("isPrimeSquarerootWayArr: ", sum(isPrimeSquarerootWayArr)/len(isPrimeSquarerootWayArr))
print("primeArr: ", sum(primeArr)/len(primeArr))
print("isprimeAKSWayArr: ", sum(isprimeAKSWayArr)/len(isprimeAKSWayArr))

Sample 1 Million Iterations

Iteration 1:

isPrimeConventionalWayArr:  1749.97224997225
isPrimeSquarerootWayArr:  1835.6258356258356
primeArr (suggested):  475.2365752365752
isprimeAKSWayArr:  1177.982377982378

Iteration 2:

isPrimeConventionalWayArr:  1803.141403141403
isPrimeSquarerootWayArr:  2184.222484222484
primeArr (suggested):  572.6434726434726
isprimeAKSWayArr:  1403.3838033838033

Iteration 3:

isPrimeConventionalWayArr:  1876.941976941977
isPrimeSquarerootWayArr:  2190.43299043299
primeArr (suggested):  569.7365697365698
isprimeAKSWayArr:  1449.4147494147494

Iteration 4:

isPrimeConventionalWayArr:  1873.2779732779734
isPrimeSquarerootWayArr:  2177.154777154777
primeArr (suggested):  590.4243904243905
isprimeAKSWayArr:  1401.9143019143019

Iteration 5:

isPrimeConventionalWayArr:  1891.1986911986912
isPrimeSquarerootWayArr:  2218.093218093218
primeArr (suggested):  571.6938716938716
isprimeAKSWayArr:  1397.6471976471976

Iteration 6:

isPrimeConventionalWayArr:  1868.8454688454688
isPrimeSquarerootWayArr:  2168.034368034368
primeArr (suggested):  566.3278663278663
isprimeAKSWayArr:  1393.090193090193

Iteration 7:

isPrimeConventionalWayArr:  1879.4764794764794
isPrimeSquarerootWayArr:  2199.030199030199
primeArr (suggested):  574.055874055874
isprimeAKSWayArr:  1397.7587977587978

Iteration 8:

isPrimeConventionalWayArr:  1789.2868892868894
isPrimeSquarerootWayArr:  2182.3258823258825
primeArr (suggested):  569.3206693206694
isprimeAKSWayArr:  1407.1486071486072

When I have to do a fast verification, I write this simple code based on the basic division between numbers lower than square root of input.

def isprime(n):
    if n%2==0:
        return n==2
    else:
        cota = int(n**0.5)+1
        for ind in range(3,2,cota):
            if n%ind==0:
                print(ind)
                return False
    is_one = n==1
    return True != is_one

isprime(22783)

• The last True != n==1 is to avoid the case n=1.