Largest prime factor in C# (Sieve of Eratosthenes)
Work in progress -- todo: refactor, speed up ... this is not the most efficient implementation in the world so please take it with a grain of salt. A much more efficient implementation can be found here: http://stackoverflow.com/questions/30877/fastest-way-to-calculate-primes-in-c.
using System;
using System.Collections.Generic;
class Problem3{
public static void Main(){
Problem3 problem = new Problem3();
const long target = 600851475143;
int largestPrime = 0;
DateTime start = DateTime.Now;
List<int> primes = problem.GetPrimes(10000);
for(int i = primes.Count - 1; i >= 0; i--){
if(target % primes[i] == 0){
largestPrime = primes[i];
break;
}
}
DateTime end = DateTime.Now;
TimeSpan duration = end - start;
Console.WriteLine("Largest Prime of " + target + ": " + largestPrime);
Console.WriteLine("Time: " + duration.Milliseconds + "ms");
}
public List<int> GetPrimes(int max){
List<int> primes = new List<int>();
for(int i = 2; i < max; i++){
if(i % 2 != 0)
primes.Add(i);
}
primes.Insert(0, 2);
for(int i = 0; i < Math.Floor(Math.Sqrt(max)); i++){
int prime = primes[i];
for(int j = i+1; j < primes.Count; j++){
if(primes[j] % prime == 0){
primes.Remove(primes[j]);
}
}
}
return primes;
}
}