Pequeño teorema de Fermat

Fernando Ruiz Laguna

/*Este programa indica si un número es primo mediante el pequeño teorema de Fermat; en lugar de usar funciones recursivas*/

/*En un principio tomando a=2 parece que se hallan todos los primos pero si alguien encuentra algún contraejemplo que me lo haga saber*/

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

using namespace std;

int main()
{
int n;
int pot;
cout << (“Dame un numero: “) << endl;
cin >> n;
if(n==2) cout << “El numero ” << n << ” es primo” << endl;
else
pot = pow(2,n-1);
if(pot%n==1) cout << “El numero ” << n << ” es primo” << endl;
else cout << “El numero ” << n << ” no es primo” << endl;
system(“pause”);
return 0;

}

Anuncios
Esta entrada fue publicada en Informática e Internet. Guarda el enlace permanente.

Una respuesta a Pequeño teorema de Fermat

  1. ATENCION: Al plantear ‘pot’ como ‘int’ solo puedes ir hasta 2^16, a partir de ahí tendrás overflow así que solo puedes comprobar con garantías hasta n=16 (si ‘pot’ fuese ‘unsigned int’ entonces podrías ir hasta n=32). Te sugiero que hagas ‘pot’ bien float o bien double, pero entonces la operación módulo la deberás programar con un bucle porque el operador % solo es válido para variables ‘int’.

    En cuanto a números que verifican la igualdad del pequeño teorema de Fermat pero que no son primos creo que tienes varios ejemplos: 341, 1729, 2047… Se llaman ‘números pseudoprimos’ (sóndealo en Wikipedia).

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