Project Euler 3

 ProjectEuler, Projects  Comments Off on Project Euler 3
Aug 012012


The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

I only want to post a small snippet of code here for now, I may add the rest later, though it is fairly trivial.  This set of code is what I use to generate my prime numbers, it contains two versions.  The first version is incredibly slow as it used two nested loops that iterated through UpperBound*UpperBound times.  The second version, however, still iterates through the UpperBound once and will then only iterate through the Jth elements until i*j >UpperBound.  This change made the time necessary go from minutes to literally just a few seconds.

The algorithm starts by creating a list with count = UpperBound, so each number has a position in the list.  All the list elements except the 0th, and 1st, are set to true.  The outer loop then goes through, checking for values in the list set to true, if it find one, it will use the second loop to find all of the whole products up until i*j >UpperBound.

This algorithm was later used in my cryptographic suite that I wrote as a personal exercise during my cryptography course.  While the algorithm is fast, the inner loop could easily be parallelized to add an additional speedup if desired.

UPDATE: after reading some articles on prime numbers and better generation techniques, it appears this is a well known algorithm.  I had read about something similar to mine, but it did not have a few of the optimizations that mine does.  Regardless, it is called the Sieve of Eratosthenes, and is one of the fastest known ways to generate prime numbers.


static public List<Int64> GeneratePrimes(Int64 UpperBound)
//generate a table from 0 to UpperBound, each entry represents its index value
//ie testField[2] represents the int 2, it will be set to true to indicate that it is truly a prime number
//all multiples of 2 to UpperBound will be marked as false, since they can't be prime
//we then move to the next index, i, and if it is still marked as true, repeat
//if i is false, then try i+1

List<Int64> retVal = new List<Int64>();

bool[] testField = new bool[UpperBound + 1];

//set all entries to true for now, we will set to false iteratively
for (Int64 i = 0; i <= UpperBound; i++)
testField[i] = true;

//these can never be prime, we know
testField[0] = false;
testField[1] = false;

for (Int64 i = 2; i <= UpperBound; i++)
//check to see if this number is still marked as true, if so, its a prime
if (testField[i])
//test every other field after this to see if its a multiple
//for (Int64 j = i + 1; j <= UpperBound; j++)
// //if the mod == 0, that means its a multiple and needs ot be set to false
// if (j % i == 0)
// {
// testField[j] = false;
// }

int j = 2;
while (true)
testField[i * j] = false;


return retVal;