getPrimes2.java

// NOTE: read only comments , comments start with '//'

import java.util.*;

public class Component {
	public static void main(String[] args){
		int range = 25000; // specify the range within which we want prime numbers
		Test euler = new Test();
		euler.getPrimes(range);
		
	}
}

class Test{
	
	public void getPrimes(int range){
		boolean[] sieve = new boolean[range + 1]; 
		Arrays.fill(sieve, false); // make a list of 25001 items marked 'false' . here 'false' = 'not prime'
		
		sieve[2] = true; 
		sieve[3] = true; // since this algorithm starts at number 4  , we have to set 2 and 3 manually to true.
		
		int root = (int) Math.sqrt((double) range); // taking square root . further explained below at line beginning with 'EXPLAIN'
		
		for(int x = 1 ; x < root ; x++){
			for(int y = 1 ; y < root ; y++){
				int n = (4 * x * x) + (y * y); // quadratic equation of the form 4x^2 + y^2
				if(n <= range && (n % 12 == 1 || n % 12 == 5)){
					sieve[n] = !sieve[n]; // convert false to true , if above if condition is true
				}
				n = (3 * x * x) + (y * y); // 2nd quadratic eqn of the form 3x^2 + y^2
				if(n <= range && (n % 12 == 7)){
					sieve[n] = !sieve[n];
				}
				n = (3 * x * x) - (y * y); // 3rd quadratic eqn of the form 3x^2 - y^2
				if(n <= range && (n % 12 == 11)){
					sieve[n] = !sieve[n];
				}
			}
		}
		
		for(int n = 5 ; n < root ; n++){
			if(sieve[n]){
				int x = n * n; // get perfect squares
				for(int i = x ; i <= range ; i+=x){
					sieve[i] = false; // mark perfect squares as false since they are not primes
				}
			}
		}
		
		for(int i = 0 ; i < sieve.length ; i++){
			if(sieve[i]){ // if sieve[i] means if the value in the list at index 'i' is marked true, means that index is prime
			System.out.println(i + " " + sieve[i]); // print only that number.
			}
		}
	}
}

// EXPLAIN : we find the square root because if a number 'n' is not prime , then n = a * b , where if a , is less than square root of n , then b > square root of n . and if n % a == 0 ,then n is not prime