Find the largest Prime Factor of the number 600851475143 [closed]

I am trying to complete this challenge, which is to find the Find the largest Prime Factor of the number 600851475143.

My current solution is below:

static void Main(string[] args)
{
const long targetNumber = 600851475143;
var primeFactors = new List<long>();

for (long i = 1; i <= targetNumber; i++)
{
if(PrimeFactor(targetNumber, i))
{
}
}

var biggestPrimeFactor = primeFactors.Max();

Console.WriteLine(biggestPrimeFactor);
}

public static bool PrimeFactor(long number, long i)
{
return number % i == 0;
}


My main problem is that this is taking ages to run, but it's also not very eloquent.

How can I improve on the above?

Thanks

-

migration rejected from stackoverflow.comJul 28 at 5:54

This question came from our site for professional and enthusiast programmers. Votes, comments, and answers are locked due to the question being closed here, but it may be eligible for editing and reopening on the site where it originated.

closed as off-topic by RubberDuck, palacsint, 200_success♦Jul 28 at 5:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. Such questions may be suitable for Stack Overflow or Programmers. After the question has been edited to contain working code, we will consider reopening it." – RubberDuck, palacsint, 200_success
If this question can be reworded to fit the rules in the help center, please edit the question.

I'm trying to find the prime factor of a long in C#, not the prime number of an int in C++! –  JMK Mar 20 '12 at 19:58
Alternative algorithms - stackoverflow.com/questions/23287/prime-factors –  Reddog Mar 20 '12 at 19:58
You need to step back from the keyboard and think about the problem for a bit. There's a better way to find the largest prime factor. –  Kyralessa Mar 20 '12 at 20:06
Your program is not correct, so don't try to make it faster. There's no point in writing a fast program that gets the wrong answer. Try it with a smaller number. What does your program say the largest prime factor is of 12? (Hint: the correct answer is 3.) Until you can write a program that gets the correct answer, don't try to speed it up. –  Eric Lippert Mar 20 '12 at 20:47
@JMK: Your program as shown here in fact says 12, because it counts right up to the number itself, and that obviously divides itself with zero remainder. Some additional thoughts that might help you: (1) you only need to try primes up to the square root; and the number itself. The composite number 25, say, cannot have a largest prime factor bigger than 5, its square root. (Do you see why?) (2) If you find a prime factor, divide the big number by the prime factor. Why? Because then you just made the problem to solve smaller! –  Eric Lippert Mar 20 '12 at 23:15

Note 2 things.

1. There is at most 1 prime, bigger then sqrt(n)
2. If p1 is prime factor, then either p1 is max prime factor, or you can divide by p1, without affecting largest factor. So all in all, it gives you code.

static void Main(string[] args)

{
const long targetNumber = 600851475143;
var primeFactors = new List<long>();

for (long i = 1; i*i <= targetNumber; i++)
{
while(PrimeFactor(targetNumber, i))
{
targetNumber /= i;
}
}

var biggestPrimeFactor = primeFactors.Max();

Console.WriteLine(biggestPrimeFactor);
}

-

Gotta love Linq...

This would need to be tweaked to make it generic enough to use for any number (ie the Enumerable.Range only accepts ints) but it really shows off the power of Linq. This brings back the answer in .036 seconds on my machine.

void Main()
{
const double targetNumber = 600851475143;
var biggestPrimeFactor = Enumerable.Range(2, Convert.ToInt32(Math.Sqrt(targetNumber)))
.Reverse()
.AsParallel()
.Where(g => targetNumber % g == 0 && IsPrime(g))
.FirstOrDefault();

Console.WriteLine(biggestPrimeFactor);
}

private static bool IsPrime(int number)
{
for (int index = 2; index <= Math.Sqrt(number); index++)
if (number % index == 0) return false;
return true;
}

-

Easier solution:

static void Main(string[] args)
{
ulong n = 600851475143;
ulong i = 1;
ulong result;
while (n != 1)
{
i++;
how = 0;
while (n % i == 0)
{
n /= i;
}
}
result = i;
Console.WriteLine(result);
}

-
What's up with how = 0;? You don't define it, and you never use it. You also shouldn't need the variable result. This also doesn't take the 'easy' shortcut of iterating only to the square root - this setup isn't optimal for dealing with prime numbers. –  Clockwork-Muse Feb 4 '13 at 21:05

A few things about finding primes.

1. Prebuild in the single digit primes 2, 3, 5, & 7 (and put into step 4 if used)
2. The only numbers you need to check end with 1, 3, 7, or 9 (assuming you start after step 1)
3. For a stage 1 increase in speed, use independent parallel checking by assigned range
4. For a stage 2 increase, use a caching system to get the feed of the most up-to-date prime number list. When a prime number is found, feed it into the caching system.
5. Bridge to pure C for the heavy lifting.

Item 2 = 60% reduction in numerical checks. Just use the base numbers and multiply them by 10 for each check. (17, 27, 37, 47, etc.)

Item 3 = utilization of multiple cores, possibly multiple separate computers. You can utilize .net's parallel.foreach() for ease of use.

Item 4 = in your example, you consider it a "list" of primes found. but each thread will need to lock/unlock access. It is better for each thread to pull in the list and use it as a primer for the next check if you are using parallel prime # checking.

Item 5 = removing as much .net and windows overhead as possible.

Since you are trying to get to the largest prime given the ceiling you provided, just check backwards for each 1, 3, 7, or 9. You'll probably find it within a few seconds-minutes.

-

Rather than checking every number to see which are divisors of your target, start by finding the prime factors of the target and then simply return the largest.

The fundamental rule of arithmetic tells us that the target has a single set of prime factors. We can infer that for the target T, T = p x V where p is the first prime factor found and V is the product of all remaining factors.

What this means is that you should loop through known prime numbers, dividing the target by each prime that is a factor. Keep doing this until the target is reduced to one - and the last prime number used as a divisor is the largest.

Thus

while workingTarget > 1

if workingTarget % knownPrime = 0
workingTarget = workingTarget / knownPrime
else
next knownPrime

-