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.

Sieve of Eratosthenes

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;
        }

}

Categories

| Comments (0)TrackBacks (0)

0 TrackBacks

Listed below are links to blogs that reference this entry: Largest prime factor in C# (Sieve of Eratosthenes).

TrackBack URL for this entry: http://www.rootsilver.com/mt-tb.cgi/95

Leave a comment