Write a java program to compute all prime numbers less than

Write a java program to compute all prime numbers less than equal to a given integer N. The Sieve of Eratosthenes is a method used to compute all primes less then N. We begin by making a table of integers 2 to N. We find the smallest integer, i that is not crossed out, print i, and cross out i, 2i, 3i, ... When i > Squareroot N the algorithm terminates. Prompt the user to give an integer value of N and print all primes up till N using the above algorithm.

Solution

import java.io.*; import java.util.*; public class Solution { public static void main(String[] args)throws IOException { BufferedReader br =new BufferedReader(new InputStreamReader(System.in)); int t=Integer.parseInt(br.readLine()); int limit =Integer.parseInt(br.readLine()); boolean[] sieve = new boolean[limit + 1]; int limitSqrt = (int)Math.sqrt((double)limit); long count=0; Arrays.fill(sieve, false); sieve[0] = false; sieve[1] = false; sieve[2] = true; sieve[3] = true; for (int x = 1; x <= limitSqrt; x++) { for (int y = 1; y <= limitSqrt; y++) { int n = (4 * x * x) + (y * y); if (n <= limit && (n % 12 == 1 || n % 12 == 5)) { sieve[n] = !sieve[n]; } n = (3 * x * x) + (y * y); if (n <= limit && (n % 12 == 7)) { sieve[n] = !sieve[n]; } n = (3 * x * x) - (y * y); if (x > y && n <= limit && (n % 12 == 11)) { sieve[n] = !sieve[n]; } } } for (int n = 5; n <= limitSqrt; n++) { if (sieve[n]) { int x = n * n; for (int i = x; i <= limit; i += x) { sieve[i] = false; } } } for(int i=0; i