created on thu oct 5 16 44 23 2017 christian bender this python library contains some useful functions to deal with prime numbers and whole numbers overview isprimenumber sieveern getprimenumbersn primefactorizationnumber greatestprimefactornumber smallestprimefactornumber getprimen getprimesbetweenpnumber1 pnumber2 isevennumber isoddnumber kgvnumber1 number2 least common multiple getdivisorsnumber all divisors of number inclusive 1 number isperfectnumbernumber newfunctions simplifyfractionnumerator denominator factorial n n fib n calculate the nth fibonacci term goldbachnumber goldbach s assumption input positive integer number returns true if number is prime otherwise false isprime3 true isprime10 false isprime97 true isprime9991 false isprime1 traceback most recent call last assertionerror number must been an int and positive isprimetest traceback most recent call last assertionerror number must been an int and positive precondition 0 and 1 are none primes if number divisible by divisor then sets status of false and break up the loop precondition input positive integer n 2 returns a list of prime numbers from 2 up to n this function implements the algorithm called sieve of erathostenes sieveer8 2 3 5 7 sieveer1 traceback most recent call last assertionerror n must been an int and 2 sieveertest traceback most recent call last assertionerror n must been an int and 2 precondition beginlist contains all natural numbers from 2 up to n actual sieve of erathostenes filters actual prime numbers precondition input positive integer n 2 returns a list of prime numbers from 2 up to n inclusive this function is more efficient as function sieveer getprimenumbers8 2 3 5 7 getprimenumbers1 traceback most recent call last assertionerror n must been an int and 2 getprimenumberstest traceback most recent call last assertionerror n must been an int and 2 precondition iterates over all numbers between 2 up to n1 if a number is prime then appends to list ans precondition input positive integer number returns a list of the prime number factors of number primefactorization0 0 primefactorization8 2 2 2 primefactorization287 7 41 primefactorization1 traceback most recent call last assertionerror number must been an int and 0 primefactorizationtest traceback most recent call last assertionerror number must been an int and 0 precondition potential prime number factors if number not prime then builds the prime factorization of number precondition input positive integer number 0 returns the greatest prime number factor of number greatestprimefactor0 0 greatestprimefactor8 2 greatestprimefactor287 41 greatestprimefactor1 traceback most recent call last assertionerror number must been an int and 0 greatestprimefactortest traceback most recent call last assertionerror number must been an int and 0 precondition prime factorization of number precondition input integer number 0 returns the smallest prime number factor of number smallestprimefactor0 0 smallestprimefactor8 2 smallestprimefactor287 7 smallestprimefactor1 traceback most recent call last assertionerror number must been an int and 0 smallestprimefactortest traceback most recent call last assertionerror number must been an int and 0 precondition prime factorization of number precondition input integer number returns true if number is even otherwise false iseven0 true iseven8 true iseven287 false iseven1 false iseventest traceback most recent call last assertionerror number must been an int precondition input integer number returns true if number is odd otherwise false isodd0 false isodd8 false isodd287 true isodd1 true isoddtest traceback most recent call last assertionerror number must been an int precondition goldbach s assumption input a even positive integer number 2 returns a list of two prime numbers whose sum is equal to number goldbach8 3 5 goldbach824 3 821 goldbach0 traceback most recent call last assertionerror number must been an int even and 2 goldbach1 traceback most recent call last assertionerror number must been an int even and 2 goldbachtest traceback most recent call last assertionerror number must been an int even and 2 precondition creates a list of prime numbers between 2 up to number run variable for whileloops exit variable for break up the loops precondition least common multiple input two positive integer number1 and number2 returns the least common multiple of number1 and number2 kgv8 10 40 kgv824 67 55208 kgv1 10 10 kgv0 traceback most recent call last typeerror kgv missing 1 required positional argument number2 kgv10 1 traceback most recent call last assertionerror number1 and number2 must been positive integer kgvtest test2 traceback most recent call last assertionerror number1 and number2 must been positive integer precondition for kgv x 1 builds the prime factorization of number1 and number2 iterates through primefac1 iterates through primefac2 precondition gets the nth prime number input positive integer n 0 returns the nth prime number beginning at index 0 getprime0 2 getprime8 23 getprime824 6337 getprime1 traceback most recent call last assertionerror number must been a positive int getprimetest traceback most recent call last assertionerror number must been a positive int precondition if ans not prime then runs to the next prime number precondition input prime numbers pnumber1 and pnumber2 pnumber1 pnumber2 returns a list of all prime numbers between pnumber1 exclusive and pnumber2 exclusive getprimesbetween3 67 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 getprimesbetween0 traceback most recent call last typeerror getprimesbetween missing 1 required positional argument pnumber2 getprimesbetween0 1 traceback most recent call last assertionerror the arguments must been prime numbers and pnumber1 pnumber2 getprimesbetween1 3 traceback most recent call last assertionerror number must been an int and positive getprimesbetweentest test traceback most recent call last assertionerror number must been an int and positive precondition if number is not prime then fetch the next prime number fetch the next prime number precondition ans contains not pnumber1 and pnumber2 input positive integer n 1 returns all divisors of n inclusive 1 and n getdivisors8 1 2 4 8 getdivisors824 1 2 4 8 103 206 412 824 getdivisors1 traceback most recent call last assertionerror n must been int and 1 getdivisorstest traceback most recent call last assertionerror n must been int and 1 precondition precondition input positive integer number 1 returns true if number is a perfect number otherwise false isperfectnumber28 true isperfectnumber824 false isperfectnumber1 traceback most recent call last assertionerror number must been an int and 1 isperfectnumbertest traceback most recent call last assertionerror number must been an int and 1 precondition precondition summed all divisors up to number exclusive hence 1 input two integer numerator and denominator assumes denominator 0 returns a tuple with simplify numerator and denominator simplifyfraction10 20 1 2 simplifyfraction10 1 10 1 simplifyfractiontest test traceback most recent call last assertionerror the arguments must been from type int and denominator 0 precondition build the greatest common divisor of numerator and denominator precondition input positive integer n returns the factorial of n n factorial0 1 factorial20 2432902008176640000 factorial1 traceback most recent call last assertionerror n must been a int and 0 factorialtest traceback most recent call last assertionerror n must been a int and 0 precondition input positive integer n returns the nth fibonacci term indexing by 0 fib0 1 fib5 8 fib20 10946 fib99 354224848179261915075 fib1 traceback most recent call last assertionerror n must been an int and 0 fibtest traceback most recent call last assertionerror n must been an int and 0 precondition input positive integer number returns true if number is prime otherwise false is_prime 3 true is_prime 10 false is_prime 97 true is_prime 9991 false is_prime 1 traceback most recent call last assertionerror number must been an int and positive is_prime test traceback most recent call last assertionerror number must been an int and positive precondition 0 and 1 are none primes if number divisible by divisor then sets status of false and break up the loop precondition input positive integer n 2 returns a list of prime numbers from 2 up to n this function implements the algorithm called sieve of erathostenes sieve_er 8 2 3 5 7 sieve_er 1 traceback most recent call last assertionerror n must been an int and 2 sieve_er test traceback most recent call last assertionerror n must been an int and 2 precondition beginlist contains all natural numbers from 2 up to n this list will be returns actual sieve of erathostenes filters actual prime numbers precondition input positive integer n 2 returns a list of prime numbers from 2 up to n inclusive this function is more efficient as function sieveer get_prime_numbers 8 2 3 5 7 get_prime_numbers 1 traceback most recent call last assertionerror n must been an int and 2 get_prime_numbers test traceback most recent call last assertionerror n must been an int and 2 precondition iterates over all numbers between 2 up to n 1 if a number is prime then appends to list ans precondition input positive integer number returns a list of the prime number factors of number prime_factorization 0 0 prime_factorization 8 2 2 2 prime_factorization 287 7 41 prime_factorization 1 traceback most recent call last assertionerror number must been an int and 0 prime_factorization test traceback most recent call last assertionerror number must been an int and 0 precondition this list will be returns of the function potential prime number factors if number not prime then builds the prime factorization of number precondition input positive integer number 0 returns the greatest prime number factor of number greatest_prime_factor 0 0 greatest_prime_factor 8 2 greatest_prime_factor 287 41 greatest_prime_factor 1 traceback most recent call last assertionerror number must been an int and 0 greatest_prime_factor test traceback most recent call last assertionerror number must been an int and 0 precondition prime factorization of number precondition input integer number 0 returns the smallest prime number factor of number smallest_prime_factor 0 0 smallest_prime_factor 8 2 smallest_prime_factor 287 7 smallest_prime_factor 1 traceback most recent call last assertionerror number must been an int and 0 smallest_prime_factor test traceback most recent call last assertionerror number must been an int and 0 precondition prime factorization of number precondition input integer number returns true if number is even otherwise false is_even 0 true is_even 8 true is_even 287 false is_even 1 false is_even test traceback most recent call last assertionerror number must been an int precondition input integer number returns true if number is odd otherwise false is_odd 0 false is_odd 8 false is_odd 287 true is_odd 1 true is_odd test traceback most recent call last assertionerror number must been an int precondition goldbach s assumption input a even positive integer number 2 returns a list of two prime numbers whose sum is equal to number goldbach 8 3 5 goldbach 824 3 821 goldbach 0 traceback most recent call last assertionerror number must been an int even and 2 goldbach 1 traceback most recent call last assertionerror number must been an int even and 2 goldbach test traceback most recent call last assertionerror number must been an int even and 2 precondition this list will returned creates a list of prime numbers between 2 up to number run variable for while loops exit variable for break up the loops precondition least common multiple input two positive integer number1 and number2 returns the least common multiple of number1 and number2 kg_v 8 10 40 kg_v 824 67 55208 kg_v 1 10 10 kg_v 0 traceback most recent call last typeerror kg_v missing 1 required positional argument number2 kg_v 10 1 traceback most recent call last assertionerror number1 and number2 must been positive integer kg_v test test2 traceback most recent call last assertionerror number1 and number2 must been positive integer precondition actual answer that will be return for kgv x 1 builds the prime factorization of number1 and number2 captured numbers int both primefac1 and primefac2 iterates through primefac1 iterates through primefac2 precondition gets the n th prime number input positive integer n 0 returns the n th prime number beginning at index 0 get_prime 0 2 get_prime 8 23 get_prime 824 6337 get_prime 1 traceback most recent call last assertionerror number must been a positive int get_prime test traceback most recent call last assertionerror number must been a positive int precondition this variable holds the answer counts to the next number if ans not prime then runs to the next prime number precondition input prime numbers pnumber1 and pnumber2 pnumber1 pnumber2 returns a list of all prime numbers between pnumber1 exclusive and pnumber2 exclusive get_primes_between 3 67 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 get_primes_between 0 traceback most recent call last typeerror get_primes_between missing 1 required positional argument p_number_2 get_primes_between 0 1 traceback most recent call last assertionerror the arguments must been prime numbers and pnumber1 pnumber2 get_primes_between 1 3 traceback most recent call last assertionerror number must been an int and positive get_primes_between test test traceback most recent call last assertionerror number must been an int and positive precondition jump to the next number this list will be returns if number is not prime then fetch the next prime number fetch the next prime number precondition ans contains not pnumber1 and pnumber2 input positive integer n 1 returns all divisors of n inclusive 1 and n get_divisors 8 1 2 4 8 get_divisors 824 1 2 4 8 103 206 412 824 get_divisors 1 traceback most recent call last assertionerror n must been int and 1 get_divisors test traceback most recent call last assertionerror n must been int and 1 precondition will be returned precondition input positive integer number 1 returns true if number is a perfect number otherwise false is_perfect_number 28 true is_perfect_number 824 false is_perfect_number 1 traceback most recent call last assertionerror number must been an int and 1 is_perfect_number test traceback most recent call last assertionerror number must been an int and 1 precondition precondition summed all divisors up to number exclusive hence 1 input two integer numerator and denominator assumes denominator 0 returns a tuple with simplify numerator and denominator simplify_fraction 10 20 1 2 simplify_fraction 10 1 10 1 simplify_fraction test test traceback most recent call last assertionerror the arguments must been from type int and denominator 0 precondition build the greatest common divisor of numerator and denominator precondition input positive integer n returns the factorial of n n factorial 0 1 factorial 20 2432902008176640000 factorial 1 traceback most recent call last assertionerror n must been a int and 0 factorial test traceback most recent call last assertionerror n must been a int and 0 precondition this will be return input positive integer n returns the n th fibonacci term indexing by 0 fib 0 1 fib 5 8 fib 20 10946 fib 99 354224848179261915075 fib 1 traceback most recent call last assertionerror n must been an int and 0 fib test traceback most recent call last assertionerror n must been an int and 0 precondition this will be return
from math import sqrt

from maths.greatest_common_divisor import gcd_by_iterative


def is_prime(number: int) -> bool:
    

    
    assert isinstance(number, int) and (
        number >= 0
    ), "'number' must been an int and positive"

    status = True

    
    if number <= 1:
        status = False

    for divisor in range(2, int(round(sqrt(number))) + 1):
        
        
        if number % divisor == 0:
            status = False
            break

    
    assert isinstance(status, bool), "'status' must been from type bool"

    return status





def sieve_er(n):
    

    
    assert isinstance(n, int) and (n > 2), "'N' must been an int and > 2"

    
    begin_list = list(range(2, n + 1))

    ans = []  

    
    for i in range(len(begin_list)):
        for j in range(i + 1, len(begin_list)):
            if (begin_list[i] != 0) and (begin_list[j] % begin_list[i] == 0):
                begin_list[j] = 0

    
    ans = [x for x in begin_list if x != 0]

    
    assert isinstance(ans, list), "'ans' must been from type list"

    return ans





def get_prime_numbers(n):
    

    
    assert isinstance(n, int) and (n > 2), "'N' must been an int and > 2"

    ans = []

    
    
    for number in range(2, n + 1):
        if is_prime(number):
            ans.append(number)

    
    assert isinstance(ans, list), "'ans' must been from type list"

    return ans





def prime_factorization(number):
    

    
    assert isinstance(number, int) and number >= 0, "'number' must been an int and >= 0"

    ans = []  

    

    factor = 2

    quotient = number

    if number in {0, 1}:
        ans.append(number)

    
    elif not is_prime(number):
        while quotient != 1:
            if is_prime(factor) and (quotient % factor == 0):
                ans.append(factor)
                quotient /= factor
            else:
                factor += 1

    else:
        ans.append(number)

    
    assert isinstance(ans, list), "'ans' must been from type list"

    return ans





def greatest_prime_factor(number):
    

    
    assert isinstance(number, int) and (
        number >= 0
    ), "'number' must been an int and >= 0"

    ans = 0

    
    prime_factors = prime_factorization(number)

    ans = max(prime_factors)

    
    assert isinstance(ans, int), "'ans' must been from type int"

    return ans





def smallest_prime_factor(number):
    

    
    assert isinstance(number, int) and (
        number >= 0
    ), "'number' must been an int and >= 0"

    ans = 0

    
    prime_factors = prime_factorization(number)

    ans = min(prime_factors)

    
    assert isinstance(ans, int), "'ans' must been from type int"

    return ans





def is_even(number):
    

    
    assert isinstance(number, int), "'number' must been an int"
    assert isinstance(number % 2 == 0, bool), "compare must been from type bool"

    return number % 2 == 0





def is_odd(number):
    

    
    assert isinstance(number, int), "'number' must been an int"
    assert isinstance(number % 2 != 0, bool), "compare must been from type bool"

    return number % 2 != 0





def goldbach(number):
    

    
    assert (
        isinstance(number, int) and (number > 2) and is_even(number)
    ), "'number' must been an int, even and > 2"

    ans = []  

    
    prime_numbers = get_prime_numbers(number)
    len_pn = len(prime_numbers)

    
    i = 0
    j = None

    
    loop = True

    while i < len_pn and loop:
        j = i + 1

        while j < len_pn and loop:
            if prime_numbers[i] + prime_numbers[j] == number:
                loop = False
                ans.append(prime_numbers[i])
                ans.append(prime_numbers[j])

            j += 1

        i += 1

    
    assert (
        isinstance(ans, list)
        and (len(ans) == 2)
        and (ans[0] + ans[1] == number)
        and is_prime(ans[0])
        and is_prime(ans[1])
    ), "'ans' must contains two primes. And sum of elements must been eq 'number'"

    return ans





def kg_v(number1, number2):
    

    
    assert (
        isinstance(number1, int)
        and isinstance(number2, int)
        and (number1 >= 1)
        and (number2 >= 1)
    ), "'number1' and 'number2' must been positive integer."

    ans = 1  

    
    if number1 > 1 and number2 > 1:
        
        prime_fac_1 = prime_factorization(number1)
        prime_fac_2 = prime_factorization(number2)

    elif number1 == 1 or number2 == 1:
        prime_fac_1 = []
        prime_fac_2 = []
        ans = max(number1, number2)

    count1 = 0
    count2 = 0

    done = []  

    
    for n in prime_fac_1:
        if n not in done:
            if n in prime_fac_2:
                count1 = prime_fac_1.count(n)
                count2 = prime_fac_2.count(n)

                for _ in range(max(count1, count2)):
                    ans *= n

            else:
                count1 = prime_fac_1.count(n)

                for _ in range(count1):
                    ans *= n

            done.append(n)

    
    for n in prime_fac_2:
        if n not in done:
            count2 = prime_fac_2.count(n)

            for _ in range(count2):
                ans *= n

            done.append(n)

    
    assert isinstance(ans, int) and (
        ans >= 0
    ), "'ans' must been from type int and positive"

    return ans





def get_prime(n):
    

    
    assert isinstance(n, int) and (n >= 0), "'number' must been a positive int"

    index = 0
    ans = 2  

    while index < n:
        index += 1

        ans += 1  

        
        
        while not is_prime(ans):
            ans += 1

    
    assert isinstance(ans, int) and is_prime(
        ans
    ), "'ans' must been a prime number and from type int"

    return ans





def get_primes_between(p_number_1, p_number_2):
    

    
    assert (
        is_prime(p_number_1) and is_prime(p_number_2) and (p_number_1 < p_number_2)
    ), "The arguments must been prime numbers and 'pNumber1' < 'pNumber2'"

    number = p_number_1 + 1  

    ans = []  

    
    
    while not is_prime(number):
        number += 1

    while number < p_number_2:
        ans.append(number)

        number += 1

        
        while not is_prime(number):
            number += 1

    
    assert (
        isinstance(ans, list)
        and ans[0] != p_number_1
        and ans[len(ans) - 1] != p_number_2
    ), "'ans' must been a list without the arguments"

    
    return ans





def get_divisors(n):
    

    
    assert isinstance(n, int) and (n >= 1), "'n' must been int and >= 1"

    ans = []  

    for divisor in range(1, n + 1):
        if n % divisor == 0:
            ans.append(divisor)

    
    assert ans[0] == 1 and ans[len(ans) - 1] == n, "Error in function getDivisiors(...)"

    return ans





def is_perfect_number(number):
    

    
    assert isinstance(number, int) and (
        number > 1
    ), "'number' must been an int and >= 1"

    divisors = get_divisors(number)

    
    assert (
        isinstance(divisors, list)
        and (divisors[0] == 1)
        and (divisors[len(divisors) - 1] == number)
    ), "Error in help-function getDivisiors(...)"

    
    return sum(divisors[:-1]) == number





def simplify_fraction(numerator, denominator):
    

    
    assert (
        isinstance(numerator, int)
        and isinstance(denominator, int)
        and (denominator != 0)
    ), "The arguments must been from type int and 'denominator' != 0"

    
    gcd_of_fraction = gcd_by_iterative(abs(numerator), abs(denominator))

    
    assert (
        isinstance(gcd_of_fraction, int)
        and (numerator % gcd_of_fraction == 0)
        and (denominator % gcd_of_fraction == 0)
    ), "Error in function gcd_by_iterative(...,...)"

    return (numerator // gcd_of_fraction, denominator // gcd_of_fraction)





def factorial(n):
    

    
    assert isinstance(n, int) and (n >= 0), "'n' must been a int and >= 0"

    ans = 1  

    for factor in range(1, n + 1):
        ans *= factor

    return ans





def fib(n: int) -> int:
    

    
    assert isinstance(n, int) and (n >= 0), "'n' must been an int and >= 0"

    tmp = 0
    fib1 = 1
    ans = 1  

    for _ in range(n - 1):
        tmp = ans
        ans += fib1
        fib1 = tmp

    return ans


if __name__ == "__main__":
    import doctest

    doctest.testmod()