Factorization Trial Division (prime_fac.c) Simple program that returns the prime factorization of the input integer, \(n\). It works via trial division: if \(i=p_i\) is prime, we check if it is a factor of \(n\) by trial division into \(n/2^{k}\cdot p_2^{k_2} \cdots \cdot p_{i-1}^{k_{i-1}}\), repeating until \(p_i\) fails to divide \(n/2^k\cdot p_2^{k_2} \cdots \cdot p_{i-1}^{k_{i-1}}p_i^{k_i}\). This process is continued for all primes \(i < \sqrt{n}\). | ||

Prime Number Generation
Sieve of Eratosthenes (sieve_erato.c) Prime number sieve from the O.G. himself. The sieve begins at \(2\) and discards all multiples of \(2\) as composite numbers. It then selects the next number, which must be prime (\(3\) in this case), and discards all of its multiples. The sieve continues on in this way up to the input limit \(n\) to furnish a list of all primes less than \(n\). Trial Division (trial_division.c) Generates all the primes less than the input integer, \(n\), by trial divisions of all odd numbers less than \(\sqrt{n}\) (\(2\) is taken a priori prime). |