7

Como se lee en el titulo pues ese es el problema como tal, yo nuevo en esto y estoy aprendiendo de manera autodidacta, al buscar información encuentro cosas parecidas pero nada que se acerque a solucionar el problema.

No sé qué estoy haciendo mal o bueno se que estoy haciendo mal pero no se como corregirlo pues me esta dando los numeros pares, no primos.

public static void main(String[] args) {
       int num=0,cprim=0,n;
       Scanner TC = new Scanner (System.in);
       int []tam = new int [100];
       while (cprim==tam.length){
           num+=1;
           if (num%2!=0){
               tam[cprim]=num++; 
               cprim++;
           }
       }
       System.out.println(" ¿Cuantos numeros primos desea ver? ");
       n= TC.nextInt();
       for (int i=0; i<n; i++){
           System.out.println( tam[i]+", ");
       }
       
    }
    
}
1
  • 3
    Pues num%2!=0 va a validar si num es divisible por 2 sin residuo (es decir, si es par). Tu criterio para definir si es primo es incorrecto :)
    – Alfabravo
    Commented el 25 ago. 2021 a las 1:23

3 respuestas 3

6

la validación si es un número primo es incorrecta

if (num%2!=0)

Lo que hace esa validación es verificar si no es un número par.
Personalmente me gusta trabajar con métodos para cada acción a realizar; para tu caso voy a crear 3 métodos: 1 para validar si es un número primo, 1 para mostrar los números primos y el método main.

Te dejo el código comentado

public class NumerosPrimos {
    static int[]vectorPrimos;
    
    public static void main(String[] args) {    
        int contador = 0; //Para validar la cantidad de números primos
        vectorPrimos=new int[100]; //vector para guardar los 100 números primos
        int i=2; //el primer número a evaluar si es primo
        
        Scanner sc=new Scanner(System.in);
        while(contador<100){            
            if(esPrimo(i)){
                vectorPrimos[contador]=i;
                contador++; //incrementamos por cada número primo
            }
            i++; //siguiente número a evaluar si es primo            
        } 
        
        System.out.println("Cuanto primos desea mostrar");
        mostrarPrimos(sc.nextInt()); 
    }
    
    public static boolean esPrimo(int numero){
        int contador = 2;
        boolean primo=true;
        while ((primo) && (contador!=numero)){
          if (numero % contador == 0) //validamos cuando no es primo
            primo = false;
          contador++;
        }
        return primo;
    }
    
    public static void mostrarPrimos(int cantidad){
        for(int i=0;i<cantidad;i++){
            System.out.print(vectorPrimos[i]+", "); //mostramos los primos
        }
    }
}

vectorPrimos es variable de clase para acceder desde cualquier método de la clase.

Observación
Para esta oportunidad he creado la variable de clase y los métodos de forma static para no tener que crear un objeto de la clase NumerosPrimos sino llamar a los métodos de forma directa.

4

Puedes mejorar el bastante la rapidez de tu programa si aplicas algoritmos para hallar los números primos, en este caso sugiero el algoritmo de Atkin

Matemáticamente deben de cumplirse algunas condiciones matemáticas, las cuales se explican en los métodos applyWheelFactorization y discardSquarePerfects

Con ello generamos un arreglo booleano el cual podemos consultar rápidamente para saber si un número es primo. Sin embargo, este método está limitado al tamaño del arreglo, no a los números primos que realmente quieres. El pro de esto, es que tienes un performance mucho mayor que en otros métodos.

Código propuesto

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class StackOverflow {

    public static void main(String[] args) {

        SieveOfAtkin sieveOfAtkin = new SieveOfAtkin(600);
        int n = 100;
        try {
            System.out.println(sieveOfAtkin.getNPrimeArray(n));
        } catch (IllegalArgumentException e) {
            System.out.println("El tamiz de Atkin actual tiene menos de " + n +" números primos");
        }

    }

    private static class SieveOfAtkin {
        private final int limit;
        private final int sqrt_limit;
        private boolean[] sieve;

        public SieveOfAtkin(int limit) {
            this.limit = limit;
            this.sqrt_limit = (int) Math.sqrt(limit);
            initSieve();
        }

        /**
         * Devuelve el valor booleano de {@code sieve[number]}
         * @param number prime number
         * @return {@code sieve[number]}
         */
        public boolean isPrime(int number) {
            if (number > limit)
                throw new IllegalArgumentException("The argument \"number\" must be lesser than \"limit\"");
            if (number < 1)
                throw new IllegalArgumentException("There are not negative primes");
            return sieve[number];
        }

        /**
         * Este método retorna una lista con los primeros {@code n_primes} números primos
         * limitado a su existencia dentro de {@code limit}
         * @param n_primes indica cuántos números primos deseas obtener
         * @return una lista con los primeros {@code n_primes} números primos
         * limitado a su existencia dentro de {@code limit}
         * @throws IllegalArgumentException si hay menos de n números primos
         */
        private List<Integer> getNPrimeArray(int n_primes) throws IllegalArgumentException{
            return IntStream.range(2, Integer.MAX_VALUE)
                    .filter(this::isPrime)
                    .limit(n_primes)
                    .boxed()
                    .collect(Collectors.toList());
        }

        public void initSieve() {
            this.sieve = new boolean[limit];
            Arrays.fill(sieve, false);
            // SieveOfAtkin funciona únicamente con números mayores a 3
            for (int i = 2; i < 4 && i < limit; i++)
                sieve[i] = true;

            applyWheelFactorization();
            discardSquarePerfects();
        }

        /**
         * Cambia sieve[n] a verdadero si alguna de las siguientes
         * condiciones se cumple para un par de números enteros
         * cualesquiera { (x, y) | x <= sqrt_limit ∩ y <= sqrt_limit }:
         *     a) Con n = (4 * x * x) + (y * y) tenga un número impar de
         *          soluciones a la ecuación n % 12 = 1 o n % 12 = 5.
         *     b) Con n = (3 * x * x) + (y * y) tenga un número impar de
         *          soluciones a la ecuación n % 12 = 7
         *     c) Con n = (3 * x * x) - (y * y) | x > y tenga un número impar de
         *            soluciones a la ecuación and n % 12 = 11
         */
        public void applyWheelFactorization() {
            for (int x = 1; x <= sqrt_limit; x++) {
                for (int y = 1; y <= sqrt_limit; y++) {
                    // first quadratic using m = 12 and r in R1 = {r : 1, 5}
                    int n = (4 * x * x) + (y * y);
                    if (n < limit && (n % 12 == 1 || n % 12 == 5)) {
                        sieve[n] = !sieve[n];
                    }
                    // second quadratic using m = 12 and r in R2 = {r : 7}
                    n = (3 * x * x) + (y * y);
                    if (n < limit && (n % 12 == 7)) {
                        sieve[n] = !sieve[n];
                    }
                    // third quadratic using m = 12 and r in R3 = {r : 11}
                    n = (3 * x * x) - (y * y);
                    if (x > y && n < limit && (n % 12 == 11)) {
                        sieve[n] = !sieve[n];
                    } // end if
                }
            }
        }

        /**
         * Descarta todos los cuadrados perfectos como números primos, pues
         * {@link #applyWheelFactorization() applyWheelFactorization}
         * sólo elimina algunos de ellos
         */
        public void discardSquarePerfects() {
            for (int r = 5; r * r < limit; r++) {
                if (sieve[r]) {
                    for (int i = r * r; i < limit; i += r * r)
                        sieve[i] = false;
                }
            }
        }
    }

}

Comparación de eficiencia

Comparación de performance con el algoritmo propuesto por HowToDoInJava

Resultados de ejecución de los métodos getNPrimeArray en tiempo (nano segundos):

Intento HTDIJ Atkins Gana
1 15738900 06870199 Atkins
2 13388100 05334699 Atkins
3 10170100 05314299 Atkins

Como ven la ejecución tarda menos de la mitad en completarse. Los test se corrieron por separado para evitar desventajas de ejecución y para ello se usó el siguiente código de HowToDoInJava:

private static class HowToDoInJavaAlgorithm {
    private List<Integer> getNPrimeArray(int n_primes) {
        return IntStream.range(2, Integer.MAX_VALUE)
                .filter(this::isPrime)
                .limit(n_primes)
                .boxed()
                .collect(Collectors.toList());
    }

    private boolean isPrime(int number) {
        if(number <= 2)
            return number == 2;
        else
            return  (number % 2) != 0
                    &&
                    IntStream.rangeClosed(3, (int) Math.sqrt(number))
                            .filter(n -> n % 2 != 0)
                            .noneMatch(n -> (number % n == 0));
    }
}

Lo más importante a ver es que getNPrimeArray es un método bastante tardado, pues genera una Lista, por lo cual no es tan útil para la comparación de eficiencia, por lo tanto, ahora compararemos los métodos isPrime para ver la verdadera diferencia, además de su otra ventaja, pues una vez generado el arreglo o el sieve, se puede usar mucho más rápido para obtener los n números primos.

Si ejecutamos el siguiente código podremos ver la notoria diferencia.

import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class StackOverflow{

    static final int max = 15_000;
    static final int min = 100;
    static final int n_test = 100_000;

    public static void main (String... args) {
        Random random = new Random();
        int[] numbers2check = random.ints(n_test, min, max + 1).toArray();

        Thread htdij = new Thread(() -> testHtdinjEfficiency(numbers2check));
        Thread atkins = new Thread(() -> testAtkinsEfficiency(numbers2check));

        htdij.start();
        atkins.start();
    }

    public static void testHtdinjEfficiency(int[] random) {
        long[] timing = new long[random.length];
        long start = System.nanoTime();
        HowToDoInJavaAlgorithm howToDoInJavaAlgorithm = new HowToDoInJavaAlgorithm();
        howToDoInJavaAlgorithm.isPrime(random[0]);
        timing[0] = System.nanoTime() - start;

        for (int i = 1; i < random.length; i++) {
            start = System.nanoTime();
            howToDoInJavaAlgorithm.isPrime(random[i]);
            timing[i] = System.nanoTime() - start;
        }

        Arrays.sort(timing);

        double average = Arrays.stream(timing).average().orElse(Double.NaN);
        long frequency_50 = Arrays.stream(timing).filter(e -> e <= 50).count();

        System.out.println("htdij\n======\nMin: " + timing[0] + "\tMax: " + timing[random.length -1] +
                "\tAverage: " + average + "\nFrequency(n <= 50): " + frequency_50);
    }

    public static void testAtkinsEfficiency(int[] random) {
        long[] timing = new long[random.length];

        long start = System.nanoTime();
        SieveOfAtkin sieveOfAtkin = new SieveOfAtkin(max + 1);
        sieveOfAtkin.isPrime(random[0]);
        timing[0] = System.nanoTime() - start;

        for (int i = 1; i < random.length; i++) {
            start = System.nanoTime();
            sieveOfAtkin.isPrime(random[i]);
            timing[i] = System.nanoTime() - start;
        }

        Arrays.sort(timing);

        double average = Arrays.stream(timing).average().orElse(Double.NaN);
        long frequency_50 = Arrays.stream(timing).filter(e -> e <= 50).count();

        System.out.println("Atkins\n======\nMin: " + timing[0] + "\tMax: " + timing[random.length -1] +
                "\tAverage: " + average + "\nFrequency(n <= 50): " + frequency_50);

    }
}

Mínimo

Intento HTDIJ Atkins Gana
1 0 0 Empate
2 0 0 Empate
3 0 0 Empate

Máximo

Intento HTDIJ Atkins Gana
1 6536600 3305800 Atkins
2 18481000 3475000 Atkins
3 25963700 4422100 Atkins

Promedio (redondeado)

Intento HTDIJ Atkins Gana
1 776 168 Atkins
2 1399 167 Atkins
3 1236 143 Atkins

Frecuencia (timing < 50 ns)

Intento HTDIJ Atkins Gana
1 11110 20813 Atkins
2 15974 28628 Atkins
3 17932 30261 Atkins
2

A ver si te sirve, lo que hace el código es generar los números primos hasta el número que se le pida

public static void main(String[] args) {
    //instanciamos la clase scanner
    Scanner teclado = new Scanner(System.in);
    //pedimos el número hasta el que deseamos conocer los primero
    System.out.print("Hasta que número desea saber los números primos: ");
    //recogemos el número en la variable entera
    int max = teclado.nextInt();

    //imrpimimos el texto
    System.out.println("Son números primos: ");
    //creamos un bucle for con el límite del número introducido
    for(int i = 0; i <= max; i++){
        //recogemos en una variable booleana el return del método esPrimo y enviamos el número
        //correpondiente a la iteración del bucle
        boolean primo = esPrimo(i);
        //si el return es primo, lo sacamos por pantalla
        if (primo){
            System.out.print(i + ", ");
        }
    }
    System.out.println("");
}
//método que nos dice si el número es primo que recibe por parámetro un entero (el de la iteración del bucle)
public static boolean esPrimo(int numero) {
    // El 0, 1 y 4 no son primos
    if (numero == 0 || numero == 1 || numero == 4) {
        //por lo que en esos números retonramos false
        return false;
    }
    //creamos un bucle para evaluar los números recibidos
    for (int x = 2; x < numero / 2; x++) {
        // Si es divisible por cualquiera de estos números, no es primo
        if (numero % x == 0)
            //si no es primo retornamos falso
            return false;
    }
    // Si no se pudo dividir por ninguno de los de arriba, sí es primo
    return true;
}

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.