I was recently introduced to Project Euler. This site contains many problems for programmers to test both their math skills and coding skills. One of the problems dealt with finding the largest prime factor of a very large number. I enjoyed this problem, and decided to make a small program in C# to find the prime factorization of ANY number between 2 and 9,223,372,036,854,775,807 (the highest value stored in long). The speed for the high end isn't great and would be improved if the program used an existing list of prime numbers. The program does just fine for reasonable input values, however, and the algorithm is a good tool for those wishing to have a quick prime factorization tool.
I broke the problem down into two parts. The first part is how to generate a sequence of prime numbers. The second part is finding the prime factorization using the list. Since my program does not know what the highest prime number is until the process is completed, I only generate new prime numbers as factorization candidate as needed.
Generating a sequence of primes is the first step. A prime number, be definition, is only divisible by 1 and itself. It has no other factors. All non-prime numbers can be broken out into a factorization of primes. For example, 10 is not prime as it is divisible by 1, 2, and 5. The prime factorization of 10 is 2 * 5. Since all non-prime numbers have a prime factorization, any non-prime number that is a factor of another number ensures that the primes in the prime factorization of the lower number are also factors of the higher number. For example, 10 is a factor of 20 and 10 is not prime. Since the prime factorization of 10 is 2 * 5, we know that 2 and 5 are both factors of 20. Using these deductions, we can generate a list of primes merely by testing numbers against all known primes that are lower than the given number.
I wrote a method that does exactly that. Given a list, it will populate that list with the next prime number in the sequence. See the code below, the method is named
generateNextPrime. It takes in a list as the only . argument. The only prime number that is hard-coded is 2. When an empty list is passed in, 2 is seeded as the first prime. All subsequent primes in the list are discovered. When the list is not empty, the method determines the last prime in the list and then starts at the very next number. For example, if the list contains { 2 }, then the method will start searching for the next prime at 3. The method compares the number to all discovered primes. Since 2 is greater than the square root of 3, we know that 3 is prime. The list now contains { 2, 3 } as prime numbers. The next time the method is invoked, it will start at 4. 2 is a factor of 4, so 4 is not prime and is not added to the list. The method then moves to 5. Both 2 and 3 are not factors of 5, so we add 5 to the list as prime. The list now contains { 2, 3, 5 }.This method is known as trial division. It is a lot of work if done by hand, but computers are great at doing monotonous, high-volume calculations like this quickly.
The next part of the problem is to find the prime factorization of a given number. I used trial division again to accomplish this. A list is generated that contains prime numbers to use as candidate factors. A second list is used to store numbers that are actual prime factors of the target. A prime number is generated, in sequence, one at a time and tested against the target. When a prime factor is found, the target is reduced by dividing it by the given factor and the factor is added to the list of prime factors. The prime is checked again to see if it appears in the prime factorization multiple times (such 20, which has a prime factorization of 2 * 2 * 5). Each time the target is reduced as a prime factor is found, and when the prime fails as a candidate, the program generates the next prime in sequence to test as a prime factor candidate.
Here are some screenshots of the console program in action, using inputs 10, 20, 65, and 1,234,567,890
class Program
{
static void Main(string[] args)
{
//The target number to generate a prime factorization for.
long target;
//List to store the prime factors of the target.
List<long> primeFactorList = new List<long>();
//List to store all primes. Generated as needed.
List<long> candidateList = new List<long>();
//Seed the candidateList with 2 as the first prime.
generateNextPrime(candidateList);
//Get the target number.
Console.Write("Please enter a number to generate a prime factorization for: ");
string userInput = Console.ReadLine();
//Validate input is a valid long number. If not, get new input.
while (long.TryParse(userInput, out target) == false || target < 2)
{
Console.Write("\nPlease enter a positive number greater than 1: ");
userInput = Console.ReadLine();
}
//Main while loop. Once the target is 1, we know that we have found all the prime factors.
while (target > 1)
{
//The value of the index at the last prime discovered in our candidate list.
int lastIndex = candidateList.Count - 1;
Console.WriteLine("\nChecking against prime number " + candidateList[lastIndex]);
if (target % candidateList[lastIndex] == 0)
{
//Our target is divisible by the prime number candidate. Add this to the prime factorization list and reduce
//our target by dividing it by this prime factor.
target = target / candidateList[lastIndex];
primeFactorList.Add(candidateList[lastIndex]);
Console.WriteLine("\nPrime number " + candidateList[lastIndex] + " added as a prime factor.");
}
else
{
//Our target was not divisible by the current prime number candidate. Find the next prime candidate to test.
generateNextPrime(candidateList);
}
}
//All prime factors have been found by this point in the program. Now we just need to output the prime factorization.
if (primeFactorList.Count == 1)
{
//1 prime factor.
Console.WriteLine("\nThe number is prime.");
}else
{
//Multiple prime factors
Console.Write("\nThe prime factors are: ");
foreach (long primeFactor in primeFactorList)
{
Console.Write(primeFactor);
if (primeFactor < primeFactorList[primeFactorList.Count - 1]) Console.Write(" * ");
}
}
Console.Write("\n\nPlease press any key to close...");
Console.ReadKey();
}
static private void generateNextPrime(List<long> primeList)
{
//This method will generate the next prime number in the sequence of all primes stored in primeList. The method uses trial division by comparing
//the candidate number to all previous primes.
//If the list is empty, seed it with 2 as the first prime in the sequence.
if (primeList.Count == 0)
{
primeList.Add(2);
return;
}
//Find the last prime in the discovered sequence. Start looking for a new prime at the very next number.
long lastPrime = primeList[primeList.Count - 1] + 1;
bool foundPrime = false;
//Loop until the next prime is found.
while (foundPrime == false)
{
bool notPrime = false;
//Compare the candidate number to all previous discovered primes. If the candidate is not divisible by any of the primes, then its prime factorization
//will be 1 and itself, which means it is indeed prime.
for (int x = 0; x < primeList.Count; x++)
{
if (lastPrime % primeList[x] == 0)
{
//This number is divisible by a previously discovered prime number. It is not prime.
notPrime = true;
continue;
}
}
if (notPrime == false)
{
//The number is prime. Add it to the prime list and flag the while loop to stop.
foundPrime = true;
primeList.Add(lastPrime);
}
else
{
//The number was not prime. Try the next number.
lastPrime++;
}
}
}
}
No comments:
Post a Comment