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

DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 1 of 1

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

  1. #1
    Join Date
    May 2005

    Lightbulb 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

    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.

    * 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;
    		BufferedReader keyboard =
    			new BufferedReader(new InputStreamReader(System.in));
    		System.out.print("Enter a maximum number please: ");
    		maxNum = Integer.parseInt(keyboard.readLine());
    		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++){
    				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
HTML5 Development Center
Latest Articles
Questions? Contact us.
Web Development
Latest Tips
Open Source

   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center