//01151424 David Karasz
public class Bsp06 {


    public static void main(String[] args) {
        System.out.println("Alle Primzahlen in [m, n]");
        System.out.print("m: ");
        int m = SavitchIn.readInt();
        System.out.println();
        System.out.print("n: ");
        int n = SavitchIn.readInt();
        System.out.println();
        System.out.println(String.format("Alle Primzahlen in [%d, %d]:", m, n));



        boolean[] primes = findPrimes(m, n);
        int primesCount = printPrimes(primes, m);
        System.out.println("Insgesamt: " + primesCount + " Primzahlen.");

        boolean [] Eratos = sieveOfEratosthenes (n,m);
        int primeEratos = printPrimes(Eratos, m);
        System.out.println("Insgesamt: " +primeEratos + "Primzahlen");
    }



    public static boolean isPrime(int n) {
        int prim = 2;

        while((prim <= n) && (n%prim != 0) && (n > 1))
            prim++;

        return prim == n;
    }


    public static boolean[] findPrimes(int m, int n) {
        if (n < m) return null;
        int size = n - m + 1;
        boolean[] primes = new boolean[size];
        for (int i = m; i <= n; i++) {
            primes[i - m] = isPrime(i);
        }
        return primes;
    }

    public static int printPrimes(boolean[] foundPrimes, int m) {
        int primes = 0;
        for (int i = 0; i < foundPrimes.length; i++) {
            if (foundPrimes[i]) {
                System.out.print(m + i + " ");
                primes++;
            }
        }
        System.out.println();
        return primes;
    }

    public static boolean [] sieveOfEratosthenes(int n, int m){
        boolean prime[] = new boolean[n+1];
        if (n == 0)
            prime[0] = false;
         if (n == 1)
             prime[1] = false;

        for(int i =m; m <= n; i++, m++)
             prime[i] = isPrime(m);

        for(int p = 2; p*p <=n; p++)
        {
            // If prime[p] is not changed, then it is a prime
            if(prime[p] == true)
            {
                // Update all multiples of p
                for(int i = m = p*2; i <= n; i += p)
                    prime[i] = false;
            }
        }

        // Print all prime numbers
        for(int i = 2; i <= n; i++)
        {
            if(prime[i] == true)
                System.out.print(i + " ");
        }
        return prime;
    }

}