jueves, 23 de septiembre de 2010

Saber si un numero es primo : C

Hace unos meses publiqué el código de un programa que calculaba muy rápido todos los números primos desde cero a un numero dado.[IR]

Hoy pongo otro parecido, basado en el anterior pero que calcula y dice si un numero es primo o no.

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
top:

    unsigned int x, i = 3, j, n = 2, d,max;
    cin >> x;
    cin.clear();

    if (x < 2)
        cout << x << " no es mayor que 1." << endl;
    else if (x < 4)
        cout << x << " es primo." << endl;
    else if (x%2 == 0)
        cout << x << " no es primo." << "  Es divisible por 2" << endl;
    else if (x%3 == 0)
        cout << x << " no es primo." << "  Es divisible por 3" << endl;
    else
    {
        int * p = new int[x/3];
        max = int(sqrt(x));
        p[0] = 2;
        p[1] = 3;

        while (i < max)
        {
            d = int(sqrt(i+=2));
            j = 1;
            while (d >= p[j] && i%p[j]) j++;
            if (d < p[j])
            {
                p[n++] = i;
                if (x%i == 0)
                {
                    cout << x << " no es primo." <<endl<< "  Es divisible por " << i << endl;
                    goto top;
                }
            }
        };
        cout << x << " es primo" << endl;
    }
    cout << endl;
    goto top;
};

Comparte o puntua esta publicación ▼

0 comentarios:

Publicar un comentario