Programming Challenge - Primes

Create a class that finds primes as fast as possible

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

38 Replies - 8228 Views - Last Post: 19 September 2010 - 08:56 AM

#1 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Programming Challenge - Primes

Posted 06 November 2009 - 06:17 PM

Problem: Create a class that generates all the prime numbers less than or equal to a specified value. Your code must be C# code, and may only use classes from the System libraries (up to .NET 3.5). You must implement the following interface:

interface IPrime {
	String Name { get; }
	int[] GetPrimes(int n);
}


To ensure that everyone has a level playing field, I'll be compiling and running the code on my machine which has a 3.0Ghz quad core processor with 6GB of ram. You can use any technique you like. Post your class below and I'll update the timing chart periodically. As an example, here's the output from my test process for a value of 100,000:

Momerath Slow Method ... 00:00:01.1147190

unsafe code is not allowed.

Current standings:

This post has been edited by Momerath: 06 November 2009 - 06:18 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Programming Challenge - Primes

#2 MasterDisaster  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 29-December 07

Re: Programming Challenge - Primes

Posted 15 November 2009 - 07:39 PM

Input 100000000
No. of primes 5761455
Time Taken 00:03:56.2122042

 
using System;
using System.Collections;
interface IPrime
{
	String Name { get; }
	int[] GetPrimes(int n);
}
public class Primes: IPrime
{
	string name = "MasterDisaster";

	public String Name 
	{ 
		get
		{
			return this.name;
		}
	}
	public int primeCandidate;

	public int[] GetPrimes(int n)
	{
		ArrayList primeFactors = new ArrayList();
		primeCandidate = 1;
		int inc = 1;
		while (primeCandidate <= n)
		{
			bool factor = true;
			if (primeCandidate > 2)
			{
				int r = (int)Math.Sqrt(primeCandidate);
				for (int i = 1; (int)primeFactors[i] <= r; i++)
				{
					if (primeCandidate % r == 0 || primeCandidate % (int)primeFactors[i] == 0)
					{
						factor = false;
						break;
					}
				}
				if (primeCandidate > 10 && primeCandidate % 10 == 3)
					inc = 4;
				else 
					inc = 2;
			}
			if (factor)
				primeFactors.Add(primeCandidate);
			primeCandidate += inc;
		}
		return (int[])primeFactors.ToArray(typeof(int));
	}
}


This post has been edited by MasterDisaster: 15 November 2009 - 08:03 PM

Was This Post Helpful? 0
  • +
  • -

#3 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Programming Challenge - Primes

Posted 15 November 2009 - 09:41 PM

I should post one of mine, not the best, but a one that works :
public class PrimeCheck : IPrime {
	public String Name {
		get {
			return "Momerath Prime Check";
		}
	}

	public int[] GetPrimes(int n) {
		int sqrt;
		List<int> primes = new List<int>((int)(n/Math.Log(n-1)));
		primes.Add(2);
		Boolean isPrime;
		for (int i = 3; i <= n; i += 2) {
			sqrt = (int)Math.Sqrt(i);
			isPrime = true;
			foreach (int t in primes) {
				if (t > sqrt) {
					break;
				} else if (i % t == 0) {
					isPrime = false;
					break;
				}
			}
			if (isPrime) {
				primes.Add(i);
			}
		}

		return primes.ToArray();
	}
}


This post has been edited by Momerath: 16 November 2009 - 12:14 AM

Was This Post Helpful? 0
  • +
  • -

#4 MasterDisaster  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 29-December 07

Re: Programming Challenge - Primes

Posted 16 November 2009 - 01:33 AM

Is it alright to assume the first two numbers as prime?
Was This Post Helpful? 0
  • +
  • -

#5 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Programming Challenge - Primes

Posted 16 November 2009 - 02:28 AM

You can assume any numbers are prime that you wish, though making a list of all the primes is kinda cheating. Let's say you can preload anything under 10 as a prime. This should speed up your a bit since it will remove one of your tests.

Current testing:


PrimeFinderTester
Searching the first 100,000,000 numbers for primes
Method: Math Fast Primes - Found: 5761455 - Time: 00:00:00.8218669
Method: Momerath Prime Check - Found: 5761455 - Time: 00:02:20.3767772
Method: Momerath Opt Check - Found: 5761455 - Time: 00:02:19.5063674
Method: MasterDisaster - Found: 5761456 - Time: 00:04:48.1001305

The fasted method here was not developed by me, it was developed by a PhD in math. I'm just trying to get close, say an order of magnitude, to that speed :)

This post has been edited by Momerath: 16 November 2009 - 02:37 AM

Was This Post Helpful? 0
  • +
  • -

#6 felixtgomezjr  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 3
  • View blog
  • Posts: 68
  • Joined: 04-November 09

Re: Programming Challenge - Primes

Posted 16 November 2009 - 03:38 AM

it could be a breakthrough if somebody can provide a program for finding prime numbers that will run faster than the fastest there is. So far the two programs will run in "big oh of n squared". You can also google it and see that sieve's algorithm is more efficient.
Was This Post Helpful? 0
  • +
  • -

#7 MentalFloss  Icon User is offline

  • "ADDICTED"[2:5]
  • member icon

Reputation: 527
  • View blog
  • Posts: 1,397
  • Joined: 02-September 09

Re: Programming Challenge - Primes

Posted 23 November 2009 - 09:46 PM

LOL at the name property on the interface. Clever.
Was This Post Helpful? 0
  • +
  • -

#8 StarBP  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Re: Programming Challenge - Primes

Posted 26 November 2009 - 04:54 PM

Am I allowed to preload 11 and 13 as primes? You said I could preload 10 and under, but my program requires 11 (and arguably 13) to be preloaded as primes.

EDIT: Nevermind, I'll just change it to calculate those primes instead of preloading them. I do need 2 and 3, though :)

This post has been edited by StarBP: 26 November 2009 - 04:59 PM

Was This Post Helpful? 0
  • +
  • -

#9 SixOfEleven  Icon User is offline

  • using Caffeine;
  • member icon

Reputation: 945
  • View blog
  • Posts: 6,342
  • Joined: 18-October 08

Re: Programming Challenge - Primes

Posted 26 November 2009 - 06:24 PM

I had tried this but after reading Momerath's entry I had taken the exact same approach. Will have to try and think of a new approach to solve this.
Was This Post Helpful? 0
  • +
  • -

#10 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Programming Challenge - Primes

Posted 26 November 2009 - 07:10 PM

I have one that is better than the one I posted, If I get some more submissions, I'll post it and some times :)
Was This Post Helpful? 0
  • +
  • -

#11 StarBP  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Re: Programming Challenge - Primes

Posted 26 November 2009 - 07:59 PM

I have an entry, but it would be faster if I didn't have to implement that stupid interface (Static classes allow for more optimizations by the JIT compiler). The current entry only assumes numbers under 10 to be prime. Assuming more numbers could also greatly increase the speed. A much faster, unrelated method is coming soon.

using System;
using System.Collections.Generic;

namespace PrimeNumberLister
{
    interface IPrime
    {
        String Name { get; }
        int[] Getprimes(int n);
    }

    class PrimeNumberLister : IPrime
    {
        private int listCount = 4;
        private List<int> primeNumbers = new List<int>();
        private int nextPrime = 7;
        private int[] counters = {1,2,0};

        public String Name
        {
            get { return "PrimeNumberLister"; }
        }

        public int[] Getprimes(int n)
        {
            bool isRunning = true;
            primeNumbers.Add(2);
            primeNumbers.Add(3);
            primeNumbers.Add(5);
            primeNumbers.Add(7);
            while (isRunning)
            {
                nextPrime += 2;
                while (!IsPrime(nextPrime))
                {
                    nextPrime += 2;
                }
                if (nextPrime < n)
                {
                    primeNumbers.Add(nextPrime);
                    listCount++;
                }
                if (nextPrime >= n)
                {
                    isRunning = false;
                }
            }

            return primeNumbers.ToArray();
        }

        private bool IsPrime(int number)
        {
            bool counterTriggered = false;

            counters[0] += 2;
            if (counters[0] >= 3)
            {
                counters[0] -= 3;
                if (counters[0] == 0)
                {
                    counterTriggered = true;
                }
            }

            counters[1] += 2;
            if (counters[1] >= 5)
            {
                counters[1] -= 5;
                if (counters[1] == 0)
                {
                    counterTriggered = true;
                }
            }

            counters[2] += 2;
            if (counters[2] >= 7)
            {
                counters[2] -= 7;
                if (counters[2] == 0)
                {
                    counterTriggered = true;
                }
            }

            if (counterTriggered)
            {
                return false;
            }

            if (primeNumbers.Count == 4)
            {
                return true;
            }

            int sqrt = (int)Math.Sqrt((double)number);
            int i = 4;

            while (true)
            {
                if (primeNumbers[i] > sqrt)
                {
                    return true;
                }

                if (number / primeNumbers[i] * primeNumbers[i] == number)
                {
                    return false;
                }

                i++;
            }
        }
    }
}


This post has been edited by StarBP: 26 November 2009 - 08:23 PM

Was This Post Helpful? 0
  • +
  • -

#12 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Programming Challenge - Primes

Posted 26 November 2009 - 10:07 PM

View PostStarBP, on 26 Nov, 2009 - 06:59 PM, said:

I have an entry, but it would be faster if I didn't have to implement that stupid interface

The interface allows me to create an array of methods to test, so I don't have to recode the test interface each time I try a new method.


Current Standings:
Searching the first 100,000,000 numbers for primes
Method: Math Fast Primes - Found: 5761455 - Time: 00:00:00.8461006
Method: Momerath Opt Check - Found: 5761455 - Time: 00:02:19.5572136
Method: MasterDisaster - Found: 5761456 - Time: 00:04:48.7974844
Method: Momerath BitArray - Found: 5761455 - Time: 00:00:02.9917355
Method: PrimeNumberLister - Found: 5761455 - Time: 00:02:39.8314666
Was This Post Helpful? 0
  • +
  • -

#13 StarBP  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Re: Programming Challenge - Primes

Posted 27 November 2009 - 08:18 AM

View PostMomerath, on 26 Nov, 2009 - 09:07 PM, said:

View PostStarBP, on 26 Nov, 2009 - 06:59 PM, said:

I have an entry, but it would be faster if I didn't have to implement that stupid interface

The interface allows me to create an array of methods to test, so I don't have to recode the test interface each time I try a new method.


Current Standings:
Searching the first 100,000,000 numbers for primes
Method: Math Fast Primes - Found: 5761455 - Time: 00:00:00.8461006
Method: Momerath Opt Check - Found: 5761455 - Time: 00:02:19.5572136
Method: MasterDisaster - Found: 5761456 - Time: 00:04:48.7974844
Method: Momerath BitArray - Found: 5761455 - Time: 00:00:02.9917355
Method: PrimeNumberLister - Found: 5761455 - Time: 00:02:39.8314666


Can I make it a static class? It really bugs me that the method can't be static because of the interface. Also, am I allowed to assume more primes to increase the speed? I won't assume anything over 30 as being prime. One more thing: You did say it's a Quad Core processor, right? ;)
Was This Post Helpful? 0
  • +
  • -

#14 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Programming Challenge - Primes

Posted 27 November 2009 - 10:21 AM

View PostStarBP, on 27 Nov, 2009 - 07:18 AM, said:

View PostMomerath, on 26 Nov, 2009 - 09:07 PM, said:

View PostStarBP, on 26 Nov, 2009 - 06:59 PM, said:

I have an entry, but it would be faster if I didn't have to implement that stupid interface

The interface allows me to create an array of methods to test, so I don't have to recode the test interface each time I try a new method.


Current Standings:
Searching the first 100,000,000 numbers for primes
Method: Math Fast Primes - Found: 5761455 - Time: 00:00:00.8461006
Method: Momerath Opt Check - Found: 5761455 - Time: 00:02:19.5572136
Method: MasterDisaster - Found: 5761456 - Time: 00:04:48.7974844
Method: Momerath BitArray - Found: 5761455 - Time: 00:00:02.9917355
Method: PrimeNumberLister - Found: 5761455 - Time: 00:02:39.8314666


Can I make it a static class? It really bugs me that the method can't be static because of the interface. Also, am I allowed to assume more primes to increase the speed? I won't assume anything over 30 as being prime. One more thing: You did say it's a Quad Core processor, right? ;)


As long as you implement the interface, sure. And go ahead with the prime increase, we'll see how much it improves :)
Was This Post Helpful? 0
  • +
  • -

#15 StarBP  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Re: Programming Challenge - Primes

Posted 27 November 2009 - 10:40 AM

View PostMomerath, on 27 Nov, 2009 - 09:21 AM, said:

View PostStarBP, on 27 Nov, 2009 - 07:18 AM, said:

View PostMomerath, on 26 Nov, 2009 - 09:07 PM, said:

View PostStarBP, on 26 Nov, 2009 - 06:59 PM, said:

I have an entry, but it would be faster if I didn't have to implement that stupid interface

The interface allows me to create an array of methods to test, so I don't have to recode the test interface each time I try a new method.


Current Standings:
Searching the first 100,000,000 numbers for primes
Method: Math Fast Primes - Found: 5761455 - Time: 00:00:00.8461006
Method: Momerath Opt Check - Found: 5761455 - Time: 00:02:19.5572136
Method: MasterDisaster - Found: 5761456 - Time: 00:04:48.7974844
Method: Momerath BitArray - Found: 5761455 - Time: 00:00:02.9917355
Method: PrimeNumberLister - Found: 5761455 - Time: 00:02:39.8314666


Can I make it a static class? It really bugs me that the method can't be static because of the interface. Also, am I allowed to assume more primes to increase the speed? I won't assume anything over 30 as being prime. One more thing: You did say it's a Quad Core processor, right? ;)


As long as you implement the interface, sure. And go ahead with the prime increase, we'll see how much it improves :)


I tried making it a static class with the interface implemented, but the compiler gave me an error saying that static classes can't implement interfaces.

Anyway, here's a new entry made specifically for Quad-core processors :).

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;

namespace PrimeNumberLister
{
    interface IPrime
    {
        String Name { get; }
        int[] GetPrimes(int n);
    }

    static class Program
    {
        static void Main()
        {
            Stopwatch stop = new Stopwatch();
            stop.Start();
            int[] hello = new PrimeNumberLister().GetPrimes(10000000);
            Console.WriteLine(hello.Length);
            stop.Stop();
            Console.WriteLine(stop.ElapsedMilliseconds);
        }
    }

    class PrimeNumberLister : IPrime
    {
        private int listCount = 4;
        private List<int> primes = new List<int>();
        private List<int>[] threadPrimes = new List<int>[4];
        private int nextPrime = 7;
        private int[] counters = {1,2,0};
        private volatile bool[] threadsComplete = new bool[4];
        private object locker = new object();

        public String Name
        {
            get { return "PrimeNumberLister"; }
        }

        public int[] GetPrimes(int n)
        {
            int firstThreadMin = (int)Math.Ceiling(Math.Sqrt((double)n));
            int secondThreadMin = (n / 4 + 1) / 2 * 2 + 1;
            int thirdThreadMin = (secondThreadMin * 2 + 1) / 2 * 2 + 1;
            int fourthThreadMin = (secondThreadMin * 3 + 1) / 2 * 2 + 1;
            primes.Add(2);
            primes.Add(3);
            primes.Add(5);
            primes.Add(7);
            while (nextPrime < firstThreadMin)
            {
                nextPrime += 2;
                while (!IsPrime(nextPrime))
                {
                    nextPrime += 2;
                }

                primes.Add(nextPrime);
                listCount++;
            }

            firstThreadMin = nextPrime + 2;
            ThreadStart firstThreadStart = new ThreadStart(() => ThreadMethod(firstThreadMin, secondThreadMin, 0));
            ThreadStart secondThreadStart = new ThreadStart(() => ThreadMethod(secondThreadMin, thirdThreadMin, 1));
            ThreadStart thirdThreadStart = new ThreadStart(() => ThreadMethod(thirdThreadMin, fourthThreadMin, 2));
            ThreadStart fourthThreadStart = new ThreadStart(() => ThreadMethod(fourthThreadMin, n, 3));
            Thread firstThread = new Thread(firstThreadStart);
            Thread secondThread = new Thread(secondThreadStart);
            Thread thirdThread = new Thread(thirdThreadStart);
            Thread fourthThread = new Thread(fourthThreadStart);
            threadsComplete[0] = false;
            threadsComplete[1] = false;
            threadsComplete[2] = false;
            threadsComplete[3] = false;
            firstThread.Start();
            secondThread.Start();
            thirdThread.Start();
            fourthThread.Start();
            while (!threadsComplete[0] || !threadsComplete[1] || !threadsComplete[2] || !threadsComplete[3])
            {
                Thread.Sleep(50);
            }

            primes.AddRange(threadPrimes[0]);
            primes.AddRange(threadPrimes[1]);
            primes.AddRange(threadPrimes[2]);
            primes.AddRange(threadPrimes[3]);
            return primes.ToArray();
        }

        private void ThreadMethod(int min, int max, int number)
        {
            bool isPrime = false;
            int nextPrime = min - 2;
            int[] counters = new int[3];
            int i;
            int sqrt;
            threadPrimes[number] = new List<int>();
            counters[0] = nextPrime % 3;
            counters[1] = nextPrime % 5;
            counters[2] = nextPrime % 7;
            while (nextPrime < max)
            {
                isPrime = false;
                nextPrime += 2;
                while (!isPrime)
                {
                    bool counterTriggered = false;

                    counters[0] += 2;
                    if (counters[0] >= 3)
                    {
                        counters[0] -= 3;
                        if (counters[0] == 0)
                        {
                            counterTriggered = true;
                        }
                    }

                    counters[1] += 2;
                    if (counters[1] >= 5)
                    {
                        counters[1] -= 5;
                        if (counters[1] == 0)
                        {
                            counterTriggered = true;
                        }
                    }

                    counters[2] += 2;
                    if (counters[2] >= 7)
                    {
                        counters[2] -= 7;
                        if (counters[2] == 0)
                        {
                            counterTriggered = true;
                        }
                    }

                    if (!counterTriggered)
                    {
                        sqrt = (int)Math.Sqrt((double)nextPrime);
                        i = 4;

                        while (true)
                        {
                            if (primes[i] > sqrt)
                            {
                                isPrime = true;
                                break;
                            }

                            if (nextPrime / primes[i] * primes[i] == nextPrime)
                            {
                                isPrime = false;
                                break;
                            }

                            i++;
                        }
                    }

                    if (!isPrime)
                    {
                        nextPrime += 2;
                    }
                }
                if (nextPrime < max)
                {
                    threadPrimes[number].Add(nextPrime);
                    listCount++;
                }
            }

            threadsComplete[number] = true;
        }

        private bool IsPrime(int number)
        {
            bool counterTriggered = false;

            counters[0] += 2;
            if (counters[0] >= 3)
            {
                counters[0] -= 3;
                if (counters[0] == 0)
                {
                    counterTriggered = true;
                }
            }

            counters[1] += 2;
            if (counters[1] >= 5)
            {
                counters[1] -= 5;
                if (counters[1] == 0)
                {
                    counterTriggered = true;
                }
            }

            counters[2] += 2;
            if (counters[2] >= 7)
            {
                counters[2] -= 7;
                if (counters[2] == 0)
                {
                    counterTriggered = true;
                }
            }

            if (counterTriggered)
            {
                return false;
            }

            if (primes.Count == 4)
            {
                return true;
            }

            int sqrt = (int)Math.Sqrt((double)number);
            int i = 4;

            while (true)
            {
                if (primes[i] > sqrt)
                {
                    return true;
                }

                if (number / primes[i] * primes[i] == number)
                {
                    return false;
                }

                i++;
            }
        }
    }
}


This post has been edited by StarBP: 27 November 2009 - 10:50 AM

Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3