Cálculo más eficiente de números primos

Mario Pérez Madre

/* Cálculo más eficiente de números primos

Este programa contiene otra forma distinta de calcular números primos,
pero es mucho más eficiente, ya que reduce al máximo el número de
operaciones que el ordenador debe realizar.

Se puede utilizar como base para cualquier objetivo que involucre
números primos: saber si un primo lo es o no, saber cuantos hay hasta
un número determinado (como es el caso), o en un intervalo, etc.

Por otro lado, el programa consume mucha memoria(en el ejemplo, 2MB para
calcular todos los primos del 1 al 10.000.000), pero como no es usual
trabajar con números tan grandes, no es tan importante.

Se puede modificar N, el tope hasta el que calcula el programa, pero habria
que modificar el tamaño del vector primo[], dándole un tamaño coherente.
*/

#include <iostream>
#include <cmath>

#define N 10000000

using namespace std;

unsigned int primo[1000000]; /* Al colocarlo fuera, nos evitamos problemas con la memoria dentro de main
                                El vector debe tener un tamaño coherente, deben caber todos los primos.
                                Si el programa da error o se cierra, aumenta el tamaño del vector*/

int main()
{
    unsigned int i=0, n=0, sqrtn=0, flag=0, nprimos=3; // Al ser enteros sin signo las operaciones son más rapidas
    primo[0]=2;
    primo[1]=3;
    primo[2]=5;

    cout << "TEST PRIMOS" << endl; // Hacer que el programa saque mucho texto no permite comparar la eficiencia del algoritmo

    for(n=7; n<=N; n+=2)
    {
        sqrtn=sqrt(n); // Es mucho más eficiente calcular la raíz fuera de la condicion del for
        flag=1;
        for(i=1; i<nprimos && primo[i]<=sqrtn;i++)
            if(n%primo[i]==0)
            {
                flag=0;
                break;  // No tiene sentido seguir buscando, ya no es primo
            }
        if(flag)
        {
            primo[nprimos]=n;
            nprimos++;
        }
    }
      cout << "Hay " << nprimos << " primos hasta el " << N << endl;
      return 0;
}
Anuncios
Esta entrada fue publicada en Informática e Internet. Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s