# Programming Challenge - Primes

• (3 Pages)
• 1
• 2
• 3

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

### #1 Momerath

• D.I.C Lover

Reputation: 1020
• Posts: 2,463
• 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

Reputation: 0
• 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)
primeCandidate += inc;
}
return (int[])primeFactors.ToArray(typeof(int));
}
}

```

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

### #3 Momerath

• D.I.C Lover

Reputation: 1020
• Posts: 2,463
• 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)));
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) {
}
}

return primes.ToArray();
}
}

```

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

### #4 MasterDisaster

Reputation: 0
• 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?

### #5 Momerath

• D.I.C Lover

Reputation: 1020
• Posts: 2,463
• 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

### #6 felixtgomezjr

Reputation: 3
• 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.

### #7 MentalFloss

• .

Reputation: 577
• Posts: 1,500
• Joined: 02-September 09

## Re: Programming Challenge - Primes

Posted 23 November 2009 - 09:46 PM

LOL at the name property on the interface. Clever.

### #8 StarBP

Reputation: 1
• 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

### #9 SixOfEleven

• Planeswalker

Reputation: 1055
• Posts: 6,643
• 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.

### #10 Momerath

• D.I.C Lover

Reputation: 1020
• Posts: 2,463
• 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

### #11 StarBP

Reputation: 1
• 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;

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

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

public String Name
{
}

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

}

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

{
return true;
}

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

while (true)
{
{
return true;
}

{
return false;
}

i++;
}
}
}
}

```

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

### #12 Momerath

• D.I.C Lover

Reputation: 1020
• Posts: 2,463
• Joined: 04-October 09

## Re: Programming Challenge - Primes

Posted 26 November 2009 - 10:07 PM

StarBP, 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

### #13 StarBP

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

## Re: Programming Challenge - Primes

Posted 27 November 2009 - 08:18 AM

Momerath, on 26 Nov, 2009 - 09:07 PM, said:

StarBP, 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?

### #14 Momerath

• D.I.C Lover

Reputation: 1020
• Posts: 2,463
• Joined: 04-October 09

## Re: Programming Challenge - Primes

Posted 27 November 2009 - 10:21 AM

StarBP, on 27 Nov, 2009 - 07:18 AM, said:

Momerath, on 26 Nov, 2009 - 09:07 PM, said:

StarBP, 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

### #15 StarBP

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

## Re: Programming Challenge - Primes

Posted 27 November 2009 - 10:40 AM

Momerath, on 27 Nov, 2009 - 09:21 AM, said:

StarBP, on 27 Nov, 2009 - 07:18 AM, said:

Momerath, on 26 Nov, 2009 - 09:07 PM, said:

StarBP, 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.

```using System;
using System.Collections.Generic;
using System.Diagnostics;

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

static class Program
{
static void Main()
{
Stopwatch stop = new Stopwatch();
stop.Start();
Console.WriteLine(hello.Length);
stop.Stop();
Console.WriteLine(stop.ElapsedMilliseconds);
}
}

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

public int[] GetPrimes(int 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;
{
nextPrime += 2;
while (!IsPrime(nextPrime))
{
nextPrime += 2;
}

listCount++;
}

{
}

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;
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)
{
listCount++;
}
}

}

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