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.");
}
}