DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: I wrote a Sieve of Eratosthenes program (Finding prime numbers)

1. Registered User
Join Date
May 2005
Posts
75

## Sieve of Eratosthenes

I know, I know, this topic is kind of lame but I've been having a lot of fun with it. In February I wrote my first program to find prime numbers and it simply went through every number to check if it's prime. It worked but took a very long time. In fact, I did a search for primes between 1 and 1million and it took my computer over 2 hours to finish! I'm done with my programming classes until August and decided to go back to my prime numbers. After a little research I wrote my own program using the Sieve of Eratosthenes algorithm and I'm still amazed at how fast it is. It will print all primes between 1 and 1million in seconds! I've included the program if anyone feels like testing it out

EDIT:
I've just edited the code so the array is of type boolean, this means it will calculate much larger numbers without running out of memory. I did a run of 0 - 50million without printing all of the digits and it calculated 3,001,134 prime numbers in about 45 seconds on my PC.

Code:
```/**
* SieveofEratosthenes.java
*@author srekcus (forums.devx.com) | 5-27-2005
* Find prime numbers quickly
*/

import java.io.*;

public class SieveofEratosthenes {

public static void main(String args[]) throws IOException {

int maxNum = 0;
int primeCounter = 0;
double sqrt = 0;

System.out.print("Enter a maximum number please: ");
System.out.println("\n");

maxNum++;
sqrt = Math.sqrt(maxNum);
boolean[] prime = new boolean[maxNum];

for(int i = 2; i < maxNum; i++){
prime[i] = true;
}

for(int i = 2; i <= sqrt; i++){
for(int j = i*2; j < maxNum; j+=i){
prime[j] = false;
}
}

for(int i = 0; i < prime.length; i++){
if(prime[i]){
primeCounter++;
System.out.print(i + " ");
}
}

prime = new boolean[0];

System.out.println("\n\nThere are a total of " + primeCounter + " primes in the list.");
}
}```
Last edited by srekcus; 05-29-2005 at 01:41 AM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise