1

Me han propuesto una aplicación para el móvil donde le pides la posición de un número primo y te devuelve el número primo que hay en esa posición. Yo concretamente comienzo almacenando solo los números primos en un ArrayList y despues he optimizado todo lo que se me ha ido ocurriendo para no bloquear el móvil pero al final explota, no se que más optimizaciones hacerle, si alguien me puede echar una mano por favor?, muchas gracias y un saludo a tod@s.

Aquí muestro el código:

Todo lo siguiente esta dentro de un paquete e importo las librerias correspondientes, que aquí no pongo porque me da error y no me deja publicar.

public class MainActivity extends AppCompatActivity implements View.OnClickListener {

   static ArrayList<Integer> nprimos = new ArrayList<Integer>();


    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        getSupportActionBar().setDisplayShowHomeEnabled(true);
        getSupportActionBar().setLogo(R.mipmap.ic_launcher);
        getSupportActionBar().setDisplayUseLogoEnabled(true);

        Button btnCalcular=findViewById(R.id.btnCalcular);
        btnCalcular.setOnClickListener(this);

        int numero=2;
        boolean primo=false;
        nprimos.add(1);//Hago un add inicial en el ArrayList

        for(int j=0;j<100000;j++){//Hago el bucle for hasta 100000 posiciones
            primo=true;
            for(int i=2; i<nprimos.size(); i++)//Hago el bucle for mientras sea menor del tamaño
                //del ArrayList
            {
                if(numero%nprimos.get(i)==0) {//divide solo entre los números primos
                    primo = false;//Si no es primo
                    break;//termina el for y salta a numero++
                }
            }
            if(primo)
            {//Si el número es primo le añado al ArrayList
                nprimos.add(numero);
            }//incremento la variable número y sube arriba para hacer la division en el if
            //mientras j siga siendo menor de 100000
            numero++;
        }
    }

    public void onClick(View v){

        EditText ed1=findViewById(R.id.ed1);

        int num = Integer.parseInt(ed1.getText().toString());
        TextView t=findViewById(R.id.txtResultado);
        //Al pinchar ya empezamos con un ArrayList lleno de números primos
        if(num<nprimos.size()){
            t.setText("El número primo es: "+nprimos.get(num));
        }
        else{
            int contador=0;
            int limite=num-nprimos.size();
            int numero=nprimos.get(nprimos.size()-1);
            boolean primo=false;

            while(contador!=limite) {
                primo=true;
                for(int i=2; i<nprimos.size(); i++)
                {
                    if(numero%nprimos.get(i)==0) {
                        primo=false;
                        break;
                    }
                }
                if(primo)
                {
                    contador++;
                    nprimos.add(numero);
                }
                numero++;
            }
            t.setText("El número primo es: "+nprimos.get(num-1));
        }
    }
}
2
  • Para averiguar si un número es primo, basta con comprobar si es divisible por los primos que son menores o iguales a la raíz cuadrada de dicho número. Por ejemplo, para calcular si 39991 es primo, basta con que compruebes los primos menores a 200 (200*200 = 40000). Commented el 7 oct. 2019 a las 7:35
  • Gracias por la respuesta, cuando lo implante en android studio te digo que tal funciona.
    – Robert G.
    Commented el 8 oct. 2019 a las 11:55

3 respuestas 3

2
/*
*No entiendo bien, por que lo agregas a una colección cada primo que
*encontras, yo lo resolveria algo asi.
*/
 private boolean esPrimo(int p){
  boolean primo=true;
  for(int i=2;i<p&&primo;i++){
      //donde p sea divisible por i corta y retorna falso
      primo=p%i!=0;
  }
  return primo;
 }
 private int nextPrimo(int primo){
       int cont = primo +1;
        while(!esPrimo(cont)) {
            cont ++;
        }
        return cont;
 }
 //si pasas por parametro 1 devueve 2 si pasas 5 devuelve 11
 public int primoPos(int pos){
    int primo=2;
    for(int i=0;i<pos;i++){
        primo=nextPrimo(primo);
    } 
   return primo;
 }
 /*
 *Es similar al que hiciste vos, pero mas modularizado. Tenes que tener 
 *en cuenta que buscar primos grandes te lleva mucho tiempo de ejecución
 *es por eso que se utilizan números primos muy grandes para algunos
 *métodos de encriptación.
 *Un método que podrías usar es una programación dinámica, que a medida que
 *el usuario pida una posición de un primo, lo guardes en un archivo con
 *<pos,primo> y que el programa busque, primero en el archivo, si no esta
 *que use el método desde la posición anterior mas cercana y después lo
 *guarde en el archivo.  
 */
1
  • Gracias por la respuesta, cuando lo implante en android studio te digo que tal funciona.
    – Robert G.
    Commented el 8 oct. 2019 a las 11:55
1

No veo que el programa este de acuerdo con la pregunta.

Te dan la posicion de un numero primo y tu debes encontrar el numero primo y no al reves.

Veamos Para n = 123 cual es el numero primo que se encuentra allí?

Utilicemos la siguiente formula: 2^(n–1)(2^n – 1) es el teorema de los numeros perfectos siempre que 2^n - 1 sea un numero primo.

1
Por ejemplo: Para n dado
2^(n–1)(2n – 1)
n = 2:   2^1 × (2^2 – 1) = 6 y el primo es: 3
n = 3:   2^2 × (2^3 – 1) = 28 el primo es: 7
n = 5:   2^4 × (2^5 – 1) = 496 el primo es: 31
n = 7:   2^6 × (2^7 – 1) = 8128 el primo es: 127

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.