Write a java program to compute all prime numbers less than equal to a given int

Question

Write a java program to compute all prime numbers less than equal to a given integer N using the algorithm "Sieve of Erotosthenes" The Sieve of Eratosthenes is a method used to compute all primes less than equal to 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 2, 3, ..( actually better to start at 12 and use increments i2 + , i2 + 2i, i2 + 3i, etc until N). When i is > VN, the algorithm terminates. Prompt the user to give an positive integer value N and print all primes up till N using the above algorithm on screen Note: You have to check the validity for all kinds of inputs

Explanation / Answer

public class PrimeSieve {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);

  
        boolean[] isPrime = new boolean[n+1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        // mark non-primes <= n using Sieve of Eratosthenes
        for (int factor = 2; factor*factor <= n; factor++) {

            // if factor is prime, then mark multiples of factor as nonprime
            // suffices to consider mutiples factor, factor+1, ..., n/factor
            if (isPrime[factor]) {
                for (int j = factor; factor*j <= n; j++) {
                    isPrime[factor*j] = false;
                }
            }
        }

        // count primes
        int primes = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) primes++;
        }
        System.out.println(" number of primes <= " + n + " is " + primes);
    }
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.