Programa Java para implementar la criba de Eratóstenes para generar números primos entre un rango dado

Un número que es divisible por 1 y él mismo o un número que tiene factores como 1 y el número en sí mismo se llama número primo.

Ejemplo:

Input : from = 1, to = 20
Output: 2 3 5 7 11 13 17 19

Input : from = 4, to = 15
Output: 5 7 11 13

A. Enfoque ingenuo:

1. Defina una función llamada isprime(int n) que comprobará si un número es primo o no.
2. Ejecute un ciclo de «desde» a «hasta».
3. Dentro del ciclo for, verifique si i es primo, luego imprima el valor de i

A continuación se muestra la implementación del enfoque anterior:

// Java Program to Generate Prime
// Numbers Between Given Range
class GFG {
    public static boolean isprime(int n)
    {
        if (n == 1)
            return false;
 
        for (int i = 2; i <= Math.sqrt(n); i++)
 
            // Check if a number has factors
            // its not prime and return 0
            if (n % i == 0)
                return false;
       
        // Check if a number dont
        // have any factore
        // its prime and return 1
        return true;
    }
    public static void main(String[] args)
    {
         
        // Suppose we want to print
        // prime no.  from 1 to 20
        int from = 1, to = 20, k = 0;
        for (int i = from; i <= to; i++)
            if (isprime(i))
                System.out.print(" " + i);
    }
}

 2 3 5 7 11 13 17 19

Complejidad temporal: O(n ^3/2 )

B. Criba de Eratóstenes:

Inicialmente, suponga que todos los números del 0 al n son primos, asigne el valor de array de cada número como 1. Después de eso, elimine cada número no primo cambiando el valor de 1 a 0 en una array y, finalmente, imprima solo aquellos números cuyos el valor de la array es 1, es decir, números primos.

Acercarse: 

1. Entrada n del usuario
2. En array, complete 1 correspondiente a cada elemento
3. Haz a[0]=0 y a[1]=0 como sabemos que 0,1 no son primos
4. Suponga que el primer número (2) es primo y elimine los múltiplos de 2 (ya que los múltiplos de 2 no serán primos)
5. Continúe el paso 3 hasta la raíz cuadrada (n)
6. Imprima la lista que contiene números sin tachar (o primos).

A continuación se muestra la implementación del enfoque anterior: 

// Java Program to Implement
// Sieve of eratosthenes
// to Generate Prime Numbers
// Between Given Range
import java.util.*;
class GFG {
 
    public static void main(String[] args)
    {
        int from = 1, to = 20, i;
        boolean[] a = new boolean[to + 1];
        Arrays.fill(a, true);
 
        // 0 and 1 are not prime
        a[0] = false;
        a[1] = false;
        for (i = 2; i <= Math.sqrt(to); i++)
 
            // Check if number is prime
            if (a[i])
                for (int j = i * i; j <= to; j += i) {
                    a[j] = false;
                }
        for (i = from; i <= to; i++) {
 
            // Printing only prime numbers
            if (a[i])
                System.out.print(" " + i);
        }
    }
}

 2 3 5 7 11 13 17 19

Complejidad del tiempo: O(n log(log n))