Calcular todos los números primos raros hasta un número dado en Java

publicado por: Anonymous

Tengo el siguiente enunciado y no entiendo muy bien que es lo que pide:

Decimos que un numero n es raro cuando verifica que para cualquier número m <= n y tal que ambos son primos entre sí, resulte que m es primo (dos números son primos entre sí cuando el máximo común divisor de ambos números es la unidad). Escribe un programa que liste todos los números raros entre 3 y un valor introducido por el usuario.

El código que tengo hasta el momento es este:

import java.util.Scanner;

public class EjercicioPrimos {

public static void main(String[] args) {

    System.out.println("Introduzca un número para calcular los primos:");
    Scanner teclado = new Scanner(System.in);
    int n = teclado.nextInt();
    boolean primos;
    for (int m = 3; m < n; m++) {
        primos = mcd(n, m);
        if (primos == true) {
            System.out.println(n + " " + m + " Son primos entre si.");
        } else if (primos == false) {
            System.out.println(n + " " + m + " No son primos entre si.");
        }
    }
}

public static boolean mcd(int n, int m) {
    boolean primos = true;
    for (int i = 2; i <= n; i++) {
        if (n % i == 0 && m % i == 0) { 
            primos = false;
        }
    }
    return primos;
  }
}

Y la salida para el numero 25 por consola me calcula solo si el número introducido es primo. Sin embargo, no me lo calcula en todo el intervalo de números [1,25]:

25 3 Son primos entre si.
25 4 Son primos entre si.
25 5 No son primos entre si.
25 6 Son primos entre si.
25 7 Son primos entre si.
25 8 Son primos entre si.
25 9 Son primos entre si.
25 10 No son primos entre si.
25 11 Son primos entre si.
25 12 Son primos entre si.
25 13 Son primos entre si.
25 14 Son primos entre si.
25 15 No son primos entre si.
25 16 Son primos entre si.
25 17 Son primos entre si.
25 18 Son primos entre si.
25 19 Son primos entre si.
25 20 No son primos entre si.
25 21 Son primos entre si.
25 22 Son primos entre si.
25 23 Son primos entre si.
25 24 Son primos entre si.

solución

Después de la explicación de @user3927886 que proponia una solucion con Haskell, primos entre sí no significa que sean números primos (el 9 y el 10 son primos entre sí pero ninguno de los dos es primo – y te lo pone en el propio enunciado, mcd(n,m) = 1).

-Un ejemplo para el valor introducido 5 y verifiquemos si 5 es raro. Para verificar esto, debemos pasar por todos los enteros del 1 al 5. Si alguno de ellos es un primo de 5, pero NO es primo, entonces 5 no es raro. De lo contrario, 5 es raro (según la definición de raro). Hagamoslo:

i = 1: ¿1 es un primo de 5? Sí lo es, porque el único divisor común es 1. ¿Es 1 primo? Sí. De acuerdo. Continuamos con i = 2.

i = 2: ¿Es 2 un primo de 5? Sí lo es, porque el único divisor común es 1. ¿Es 2 primo? Sí OK. Continuar.

i = 3: ¿3 es un primo de 5? Sí, lo es, porque el único divisor común es 1. ¿Es 3 primo? Sí OK. Continuar.

i = 4: ¿4 es un primo de 5? Sí, lo es, porque el único divisor común es 1. ¿Es 4 primo? ¡NO!

Así que hemos encontrado un número i <5 que es un primo de 5 pero no primo normal. Entonces 5 no es raro y es por eso que 5 no es parte de la salida del programa.

La solución con código del problema en Java seria

import java.util.Scanner;

public class Pruebas {

    public static void main(String[] args) {


        Scanner teclado = new Scanner(System.in);
        long n;
        do{
            System.out.println("Introduce un numero para calcular los numeros raros entre 3 y ese numero, ambos inclusive:");
        n= teclado.nextLong();
        if(n<=2){
            System.out.println("Introduce un numero de nuevo valido");
        }
        }while(n<=2);

        for (long m = 3; m < n; m++) {
            boolean raro = true;
            for (long i = 2; i <= m; i++) {

                if (mcd(i, m) && !numeroPrimos(i)) {
                    raro = false;
                }
            }

            if (raro) {
                System.out.print(m + ",");
            }
        }
    }

    public static boolean mcd(long n, long m) {
        boolean primos = true;
        for (long i = 2; i <= n && i <= m; i++) {
            if (n % i == 0 && m % i == 0) {
                primos = false;
            }
        }
        return primos;
    }

    public static boolean numeroPrimos(long n) {
        boolean primo = true;
        for (long i = 2; i < n; i++) {
            if (n % i == 0) {
                primo = false;
            }
        }
        return primo;
    }

}

SALIDA: La única solución para el mayor número representable de tipo long seria la secuencia 3,4,6,8,12,18,24,30

Respondido por: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *