Prime Generator

Mabye the most important function you need for Project Euler?

Source - https://www.nayuki.io/page/project-euler-solutions another inspiration, a lot of useful functions here to learn from

Sieve of Eratosthenes

Prime Factors Function

Is Prime Function

Prime Counting Function

Returns an array where array[x] = number of primes ≤ x. See Problem 609 for a more in depth explanation. If you just want the primepi for a few numbers I recommend the SymPy primepi function

Fermat Primality Test

Implementation of Fermat Primality Test. You can choose how many test's to use, from my experience 5 tests is usually enough for all the Project Euler problems i've done!

Miller-Rabin/Miller Primality Test

Implementation of the Miller-Rabin Primality Test, It has the option of using the Miller-Rabin test with a set number of test cases, and also the Miller Primality test which is guaranteed to find a correct answer if n < 3,317,044,064,679,887,385,961,981

Fibonacci numbers Generator

Source - https://stackoverflow.com/a/23462371/14856132

Divisors Function

This function is quite fast but you can make it faster if you would like using this page

Continued Fraction Function

Euler Totient Function

Euler's Totient Function counts the positive integers up to a given integer n that are relatively prime to n

Möbius Function

Möbius function returns 0 if n is divisible by p^2, otherwise returns (-1)^k, where k is number of distinct prime factors

Legendre's Formula

Legendre's formula gives an expression for the exponent of the largest power of a prime p that divides the factorial n!

Partition Function

See Problem 76 for a more in-depth explanation, returns number of ways to partition a number goal using alist elements

Primitive Pythagorean Triplet Generator

See Problem 9 for a more in-depth explanation on the theory

k-smooth numbers

Takes 2 inputs maxprime and limit and returns a sorted list of all k-smooth numbers less than the given limit where k = maxprime.

The algorithm is very simple just keep adding new numbers to a list by multiplying them with all the other numbers in the list.

Generalized Mobius Sieve & count k power-free

I re-defined the Mobius function:

k-powerful integers

Take 3 inputs k, upper_bound, count.

The function returns all k-powerful integers less than upper_bound if count = False or if count = True it returns the number of k-powerful integers less than upper_bound

It is inspired by: https://rosettacode.org/wiki/Powerful_numbers#Python 

Chinese Remainder Theorem

Implemented using the Wikipedia page

Takes 4 inputs a1, a2, n1, n2 and computes the unique solution to the system of equations

1. x = a1 (mod n1)

2. x = a2 (mod n2)

Tonelli-Shanks Algorithm

Legendre Symbol and Tonelli–Shanks algorithm are implemented below.

These are used to solve for r in a congruence of the form r^2 ≡ n (mod p)

The source for the algorithm is here: https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python/

Graph Theory Algorithms

Simple Functions