-
Notifications
You must be signed in to change notification settings - Fork 0
Math
A number N is prime if its only divisors are 1 and N.
A number N can be determined to be prime using the following:
- If
Nis even, it is not prime (unless it is 2). - If
Nis odd, attempt to divide it by every odd number in[3, sqrt(N)]. If it is divisible by any such number, it is not prime.- A slight improvement is to divide
Nby every prime number in[3, sqrt(N)]. This requres an existing list of prime numbers.
- A slight improvement is to divide
The Sieve of Eratosthenes is used to generate a list of prime numbers less than N.
Start by considering all numbers in [2, N] to be possibly prime.
Then, for each number n in the list, mark n as prime and remove all
multiples of n, starting with n * n.
A naive approach to find the prime factors of N is to generate a list of prime
numbers smaller than N and check which ones divide N, without modifying N.
A faster approach is to divide N by its smallest prime factor, then find the
prime factors of the quotient.
Two numbers are relatively prime if their GCD is 1.
The Phi function is used to calculate how many numbers less than N are
relatively prime to N. It is expressed as:
phi(N) = N * product( 1-(1/pf) for pf in prime_factors(N) )
Java's BigInteger Class
Combinatorics deals with counting the number of ways something can be done.
- Permutations
- Combinations
- Partition of a set
- Catalan Numbers (Applicable to many, many problems!!)
- The Twelvefold Way
These are generally ad-hoc.
- Gaussian elimination can be used to solve systems of equations.