Semplice programma per calcolare numeri primi

Questo semplice programma consente di calcolare con rapidità numeri primi di piccole dimensioni, i quali possono essere utili nella realizzazione di generatori pseudorandom per il codice del gioco.

Data l'equazione y = 2x² + 2ax + a. 

Dal Teorema di Fermat si può ottenere, per ogni a intero positivo dispari, e x intero positivo.

Se y = ±1 mod a allora y è uno pseudoprimo;

Se x= ±1 mod a allora y è uno pseudoprimo.

Tuttavia per confermare che il numero calcolato sia effettivamente primo è indispensabile utilizzare un crivello, nel nostro caso si tratta del crivello di Eratostene, limitato per MCD sino alla radice quadrata di y.

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

using namespace std;
bool crivello(long int numero);

int main(int argc, char *argv[])
{
   
    long int y,a;
    char risp = 's';
   
    do {
    int n_primi =0 , p_primi =0, v_primi=0;  
    cout << "Digita coefficiente a:"; cin >> a;
    for (int n=1; n<=10000; n++){
    y = (2*n*n + 2*n*a + a);
   
    //Determina se il modulo possiede le caratteristiche corrette
    if ((y%a == 1) || (y%a == (a-1)) || (n%a == 1) || (n%a ==(a- 1))) { cout << " pseudoprimo " << endl;  p_primi++;  
        if (crivello(y)== true) { cout << "numero primo!" << endl; n_primi++; cout << "Numero calcolato:" << y << endl; }
           else cout << "non primo" << endl; 
    }
        /*else if (crivello(y)== true) {cout << "numero primo!" << endl; v_primi++;} */
      }
    cout << "Numeri primi trovati:" << n_primi << " pseudo_primi:" << p_primi << endl;
    /*cout << "Numeri primi non pseudoprimi:" << v_primi << endl;*/
    cout << "Vuoi continuare s/n:";
    cin >> risp;
    }while (risp == 's');
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

bool crivello (long int numero){
     //crivello di Eratostene
     long double radicale = sqrt(numero); //MCD sino a radice(n)
     for (long int iA =2; iA <= radicale; iA++)
         {
            if (numero%iA ==0) return false;
             }
             return true;
     }