Finding prime numbers

It’s not so hard to calculate small-ish primes. The below method is called a prime sieve, and can be done manually:

Take two, the smallest prime number.
We know that no multiples of two are prime (4, 6, 8, 10, 12 etc), so we can cross them off our list and just print two.
Then we go to 3. 3 is prime. But 6, 9, 12 and 15 can’t be, so we print 3 and cross those multiples off.
4 has been marked as not prime, so we skip it.
5 is prime, so we cross off 10, 15, 20.
so on and so forth

Computers are much better at this than humans though, so I wrote this algorithm up in java. You can find all primes up to n fairly quickly (for small values of n).

class Primes {
	public static void main(String[] args) {
		int searchMax = 16777216;
		if(args.length == 1) {
			/* Allow over-riding the maximum */
			searchMax = Integer.parseInt(args[0]);
		}
		boolean[] isprime = new boolean[searchMax];

		int i, tmp, count = 0;

		/* Initialise */
		isprime[0] = isprime[1] = false;
		for(i = 2; i < searchMax; i++) {
			isprime[i] = true;
		}

		/* Main loop */
		for(i = 2; i < searchMax; i++) {
			if(isprime[i]) {
				System.out.println(i);
				count++;
				tmp = i * 2;
				while(tmp < searchMax) {
					isprime[tmp] = false;
					tmp += i;
				}
			}
		}
		System.err.println("Found " + count + " primes between 1 and " + searchMax + " non-inclusive");
	}
}

Of course, the limitation of this is that java isn’t terribly good at handling larger arrays, so I wouldn’t expect more than a few million primes from this code.

Update: The above code was tested for finding the first 7 million prime numbers.