Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Initial Thoughts:
I had to do a bit of catching up on how to identify Prime numbers. A Prime is a number only divisible by 1 and itself. The question becomes how do we check this outside of a "brute force" method in which you just loop each subsequent number from one until the number we are checking. Especially when staring at the absurdly large number requested in the Problem.
This problem and any Prime number questions after it will come down to saving CPU cycles to more quickly and efficiently check for prime.
Right off the bat we realize that beyond the number 2, a prime will can only ever be an odd number. This alone cuts out half the numbers we will need to check for prime. We will simply start with an odd number and add two each loop iteration to keep the number we are checking odd.
Doing some further research and we will discover that the highest possible factor of a number will be equal to or less than the square root of that number (sqrt). As taking the sqrt of a number multiplied by itself will equal the whole number again. Thus our loop can simply be from one to the sqrt of the number. This enormously reduces the number of iterations our loop will need.
To illustrate further:
sqrt(100) = 10. which is 10% of 100.
sqrt(1000) = 31.622 or 3.162% of 1000
sqrt(10000) = 100 or 1.00% of 10000
sqrt(100000) = 316.227 or .3162% of 100000
sqrt(1000000) = 1000 or 0.1% of 1000000
sqrt(10000000) = 3162.27 or 0.03162% of 10000000
Look at the percentage of each number we need to check as you increase the number size. We can also see a logarithmic pattern develop.Now that we have our CPU cycle savings methods in place lets look at the rest of the question. First thing we will touch on is the sheer size of the number PE is asking us to look at.
Signed vs Unsigned data types:
For our purposes we need to know that a Signed data type can store both positive and negative numbers. Whereas an Unsigned data type can only store positive values. An INT data type is able to store 2^32 bits of data: 4,294,967,296. However because it is a Signed data type and can store negative numbers our INT data type is only able to store values between -2,147,483,648 to 2,147,483,648.
Problem 3 has us looking at a number up to 600,851,475,143 which obviously exceeds INT's capacity. I should mention to set a variable to the unsigned int type simple use "UINT" (or Unsigned INT). IE. UINT x;
int64 / long:
INT64 or LONG (I will be using LONG as I've grown accustomed to this nomenclature) stores 2^64 bits of information. They can store 18,446,744,073,709,551,616 bits of data! We should still be careful of Unsigned vs Signed data types, but even a Signed LONG will be able to store the number we are analyzing.
Final Thoughts:
I will be setting long x equal to 600851475143
I want to loop from 3 to the sqrt of x. I will be adding 2 to each loop cycle so we are only checking odd numbers. Any time the loop finds an evenly divisible number I will break the loop and output those results.
I will need a special if statement to handle a number being divisible by two.
This should provide us the least common prime least common denominators.
Solution Code:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
long x = 600851475143;
int y;
int z = 1;
int zz = 1;
int numend = 1;
Console.WriteLine("Prime Factors: ");
Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();
while(numend ==1)
{
numend = 0;
if (x % 2 != 0)
{
z = 0;
for (y = 3; y <= Math.Sqrt(x) && z < 1; y = y + 2)
{
if (x % y == 0)
{
Console.Write(y + ", ");
x = x / y;
z = 1;
numend = 1;
}
}
}
else
{
Console.Write("2, ");
x = x / 2;
numend = 1;
}
zz++;
}
stopWatch.Stop();
Console.WriteLine(x);
Console.WriteLine("Elapsed Time: " + stopWatch.ElapsedMilliseconds + " MS");
}
}
}
