A self-build module to work with integers

This post is an extension of the one named “more maths with Python”.

Since I wrote the original post I kept adding functions and improving the file containing the functions I posted. In the end I decided to use that file as a module in Python (you can check here how to build your own modules).
If you are interested in working with integers and managing big numbers in Python, you may want to try the module named gmpy2, you can easily google for it. It basically handles big numbers very fast and has many of the functions typical of number theory. It also has those showed in this post and the original one however they are much faster than the ones I made.

Anyway, here are some improvements I have made.

This function checks if n is prime. It returns True if it is, False otherwise. As you can see from its structure, it can be slow with really big numbers.

import math
def is_n_prime(n):
    i = 2
    while i <= math.sqrt(n):
        if n % i == 0:
            return False
        else:
            i += 1
    return True

The following function uses Fermat’s little theorem to check if a number n is prime. It returns True if it is probably prime, False otherwise. It may fail with Carmichael’s numbers such as 341. However its fail rate is low. It should be faster then the previous one.

def is_prime_fermat(n):
    test = (pow(3,n) - 3) % n
    if test == 0:
        return True
    else:
        return False

The function below uses the same strategy of the one above to look for prime numbers in the given range [n,q] where n < q and returns a list of primes. It is probably faster than the function I posted in the old article.

def range_primes_fermat(n,q):
    primes = []
    for i in range(n,q+1):
        test = (pow(3,i) - 3) % n
        if test == 0:
            primes.append(i)
    return primes

Here’s a function to find prime numbers less than a given number n.

def find_primes(n):
    i = 2
    primes = []
    while i <= n:
        if is_n_prime(i):
            primes.append(i)
            i += 1
        else:
            i += 1
    return primes

The function below returns the nth prime in a list of primes p, where p < n.

def find_nth_prime(n,nth):
    primes = find_primes(n)
    prime_to_return = primes[nth]
    return prime_to_return

I guess there is some way to speed them up, if that is the case, when I will find it out I am going to fix the functions and update them in a future post.

Hope this was useful! Enjoy!