Return to Answer

• The Project Euler problem asks only for the largest prime factor, so there is no need to create an array of all prime factors of the given number.
• (This is my main argument, and similar to http://codereview.stackexchange.com/a/62029/35991.) There is no need to search/test for prime numbers if you test the possible factors in increasing order and divide the given number by a found factor as much as possible, because each found factor is necessarily a prime number.

• The Project Euler problem asks only for the largest prime factor, so there is no need to create an array of all prime factors of the given number.
• (This is my main argument, and similar to https://codereview.stackexchange.com/a/62029/35991.) There is no need to search/test for prime numbers if you test the possible factors in increasing order and divide the given number by a found factor as much as possible, because each found factor is necessarily a prime number.

using System;
using System.Diagnostics; // for StopWatch
namespace FullPractice
{
 public class PrimeFactorFinder
 {
 public static void Main (string[] args)
 {
 long number = long.Parse(args[0]);
 Stopwatch stopWatch = Stopwatch.StartNew();
 long result = largestPrimeFactorOf(number);
 stopWatch.Stop();
 Console.WriteLine("Largest prime factor: {0} time: {1}ms", result, stopWatch.Elapsed.TotalMilliseconds);
 }
 static long largestPrimeFactorOf(long n)
 {
 long largestFactor = 1;
 // i is a possible *smallest* factor of the (remaining) number n.
 // If i * i > n then n is either 1 or a prime number.
 for (long i = 2; n > 1 && i * i <= n; ++i)
 {
 if (n % i == 0)
 {
 largestFactor = i;
 // Divide by the highest possible power of the found factor:
 while (n > 1 && n % i == 0)
 {
 n /= i;
 }
 }
 }
 if (n > 1)
 {
 // n is a prime number and therefore the largest prime factor of the 
 // original number.
 largestFactor = n;
 }
 return largestFactor;
 }
 }
}

On a MacBook Pro using Mono this computes the largest prime factor of 600851475143 in about 0.4 milliseconds (and with your code it takes about 6 milliseconds).

using System;
using System.Diagnostics; // for StopWatch
namespace FullPractice
{
 public class PrimeFactorFinder
 {
 public static void Main (string[] args)
 {
 long number = long.Parse(args[0]);
 Stopwatch stopWatch = Stopwatch.StartNew();
 long result = largestPrimeFactorOf(number);
 stopWatch.Stop();
 Console.WriteLine("Largest prime factor: {0} time: {1}ms", result, stopWatch.Elapsed.TotalMilliseconds);
 }
 static long largestPrimeFactorOf(long n)
 {
 long largestFactor = 1;
 // i is a possible *smallest* factor of the (remaining) number n.
 // If i * i > n then n is either 1 or a prime number.
 for (long i = 2; i * i <= n; ++i)
 {
 if (n % i == 0)
 {
 largestFactor = i;
 // Divide by the highest possible power of the found factor:
 while (n > 1 && n % i == 0)
 {
 n /= i;
 }
 }
 }
 if (n > 1)
 {
 // n is a prime number and therefore the largest prime factor of the 
 // original number.
 largestFactor = n;
 }
 return largestFactor;
 }
 }
}

On a MacBook Pro using Mono this computes the largest prime factor of 600851475143 in about 0.4 milliseconds (compared to 6 milliseconds with your code).

using System;
using System.Diagnostics; // for StopWatch
namespace FullPractice
{
 public class PrimeFactorFinder
 {
 public static void Main (string[] args)
 {
 long number = long.Parse(args[0]);
 Stopwatch stopWatch = Stopwatch.StartNew();
 long result = largestPrimeFactorOf(number);
 stopWatch.Stop();
 Console.WriteLine("Largest prime factor: {0} time: {1}ms", result, stopWatch.Elapsed.TotalMilliseconds);
 }
 static long largestPrimeFactorOf(long n)
 {
 long largestPrime = 1;
 // i is a possible *smallest* factor of the (remaining) number n.
 // If i * i > n then n is either 1 or a prime number.
 for (long i = 2; n > 1 && i * i <= n; ++i)
 {
 if (n % i == 0)
 {
 largestPrime = i;
 // Divide by the highest possible power of the found factor:
 while (n > 1 && n % i == 0)
 {
 n /= i;
 }
 }
 }
 if (n > 1)
 {
 // n is a prime number and therefore the largest prime factor of the 
 // original number.
 largestPrime = n;
 }
 return largestPrime;
 }
 }
}

using System;
using System.Diagnostics; // for StopWatch
namespace FullPractice
{
 public class PrimeFactorFinder
 {
 public static void Main (string[] args)
 {
 long number = long.Parse(args[0]);
 Stopwatch stopWatch = Stopwatch.StartNew();
 long result = largestPrimeFactorOf(number);
 stopWatch.Stop();
 Console.WriteLine("Largest prime factor: {0} time: {1}ms", result, stopWatch.Elapsed.TotalMilliseconds);
 }
 static long largestPrimeFactorOf(long n)
 {
 long largestFactor = 1;
 // i is a possible *smallest* factor of the (remaining) number n.
 // If i * i > n then n is either 1 or a prime number.
 for (long i = 2; n > 1 && i * i <= n; ++i)
 {
 if (n % i == 0)
 {
 largestFactor = i;
 // Divide by the highest possible power of the found factor:
 while (n > 1 && n % i == 0)
 {
 n /= i;
 }
 }
 }
 if (n > 1)
 {
 // n is a prime number and therefore the largest prime factor of the 
 // original number.
 largestFactor = n;
 }
 return largestFactor;
 }
 }
}