Big integer prime checking algorithm

Question

I know this is a very repetitive question on here, but I was looking to understand if I could simply check for a big integer, (eg. 157,632,829) by check if its divisible by 2, 3, 5 or 7, or am I missing corner cases?

ie.

if (n < 4) :
        return True
if (n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0) :
        return False

Oh yes! so if i include 11 and 13 into the tests it should be good to go? — TheKingSid, Oct 14 '21 at 08:22
you have to check all the prime numbers all the way up until the `sqrt(num)` — Mahrkeenerh, Oct 14 '21 at 08:24
primes are frequent, you'll have many numbers to check, otherwise you'll have `23*31`, `29*101`, `1999*2003` etc. cunterexamples — Dmitry Bychenko, Oct 14 '21 at 08:25
For really *huge* numbers, when loop (even up to `sqrt(n)`) is not an option, you can try *Rabin-Miller* test https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test — Dmitry Bychenko, Oct 14 '21 at 08:28
@DmitryBychenko, Im looking to check this in a non-probabilistic manner, any way to do so? — TheKingSid, Oct 14 '21 at 08:32
There are better *loop based* algorithms, e.g. Pollard Rho https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm; on no loops algorithms you can try Miller test https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants, Adleman–Pomerance–Rumely, — Dmitry Bychenko, Oct 14 '21 at 08:39
If you're going to implement the Miller-Rabin test then bear in mind that it determines *probable* primality and is therefore not definitive — , Oct 14 '21 at 08:47
"Big integer" is unfortunately not specific enough. Different algorithms would be used depending on the size of the number being tested, and whether probabilistic answers are acceptable. For large enough integers the algorithms are fairly complicated. — President James K. Polk, Oct 14 '21 at 19:45

score 0 · Answer 1 · answered Oct 14 '21 at 08:45

If you don't mind a looped approach then you could try this. Runs in 6ms on my machine:

import math
import time

def gen_prime():
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1


def isprime(n):
    if n >= 2:
        g = gen_prime()
        s = int(math.sqrt(n))
        while True:
            d = next(g)
            if d > s:
                return True
            if n % d == 0:
                break
    return False

s = time.perf_counter()
r = isprime(157_632_829)
e = time.perf_counter()
print(f'{r} {e-s:.4f}s')

Note: The gen_prime() generator is not mine. Unfortunately I can't remember where I got it from so can't give credit

score 0 · Answer 2 · answered Oct 22 '21 at 01:54

0

A very simple routine would be

bool isprime( int n )
{
   for( int i = 2; i < n; i++ ) if( n % i == 0 ) return false;
   return true;
}

There are lots of ways to optimize it.

answered Oct 22 '21 at 01:54

brian beuning

2,836
18
22

Big integer prime checking algorithm

2 Answers2