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
    Posts
    75

    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

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


   Development Centers

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