Mathematics5

Q5. Print all prime numbers from 1 to given number n?

Answer: 

• Brute force algo: we can iterate from 1 to n, check if a number is prime (using function from Mathematics-4), but this is not optimal solution.
• Optimal solution: Sieve of Eratosthenes 

public class Mathematics5 {
    public static void printPrimes(int n) {
        // maintain an boolean array to mark prime numbers
        boolean[] isPrime = new boolean[n + 1];

        // initially assume all integers from 2 to n are prime
        // we know that 1 is not prime
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i * i <= n; i++) {
            // if i is prime, then mark multiples of i as non prime
            if (isPrime[i]) {
                for (int j = i; i * j <= n; j++) {
                    isPrime[i * j] = false;
                }
            }
        }

        // print all primes
        for (int i = 1; i <= n; i++) {
            if (isPrime[i])
                System.out.println(i);
        }
    }

    public static void main(String[] args) {
        printPrimes(100);
    }
}