Comparing primality tests

isprime.py

#!/usr/bin/python3

def format(f):
    return int(f * 100) / 100

def isprime_6k(p):

    # Basic Test
    if (p % 2 == 0):
        return 0,1

    if (p % 3 == 0):
        return 0,2

    comps = 2

    # http://en.wikipedia.org/wiki/Primality_test
    # The algorithm can be improved further by observing that all primes are of the form
    # 6k +/- 1, with the exception of 2 and 3.
    # This is because all integers can be expressed as (6k + i) for some integer k
    # and for i = -1, 0, 1, 2, 3, or 4;
    # 2 divides (6k + 0), (6k + 2), (6k + 4);
    # and 3 divides (6k + 3).
    # So for every prime p > 3, p is of one the following forms:
    # m = 6n - 1
    # k = 6n + 1

    m = 5
    k = 7
    while (1):
        if (m * m > p):
            return 1, comps + 1
        if (p % m == 0):
            return 0, comps + 2
        if (p % k == 0):
            return 0, comps + 3
        comps += 3
        m += 6
        k += 6

def isprime_sv(p):

    # Basic Test
    if (p % 2 == 0):
        return 0,1

    if (p % 3 == 0):
        return 0,2

    comps = 2

    # Implemented logic from here
    # https://github.com/videlalvaro/erlang-prime-sv
    n = int((p - 1) / 2)
    k = 3
    res = int((k - 1) / 2)

    while (1):
        if (n < k):
            return 1, comps + 1
        if (k * k > p):
            return 1, comps + 2
        if ((n % k) == res):
            return 0, comps + 3
        comps += 3
        k += 2
        res += 1

if __name__ == "__main__":

    comps_6k_false = 0
    comps_6k_true = 0
    primes_6k = 0

    comps_sv_false = 0
    comps_sv_true = 0
    primes_sv = 0

    for num in range(5, 100001):
        check, comps = isprime_6k(num)
        if (check):
            comps_6k_true += comps
            primes_6k += 1
        else:
            comps_6k_false += comps

        check, comps = isprime_sv(num)
        if (check):
            comps_sv_true += comps
            primes_sv += 1
        else:
            comps_sv_false += comps

        if (primes_6k != primes_sv):
            print("Something went wrong at", num)

        if (num == 100 or
            num == 1000 or
            num == 10000):

            print("isprime_6k @ ", num,
                  format(comps_6k_true / primes_6k),
                  format(comps_6k_false / (num - primes_6k)))

            print("isprime_sv @ ", num,
                  format(comps_sv_true / primes_sv),
                  format(comps_sv_false / (num - primes_sv)))

results

$ python isprime.py 
isprime_6k @  100 5.08 1.54
isprime_sv @  100 10.47 2.09
isprime_6k @  1000 11.94 2.23
isprime_sv @  1000 30.83 3.91
isprime_6k @  10000 33.78 3.3
isprime_sv @  10000 96.45 7.06