Stop & Go

Télécharger le projet
Commenter

Description

La formule p = k.n - k+1 peut donner consécutivement plusieurs nombres premiers selon la valeur de n. Par exemple, pour n=3 on obtient 3, 5 et 7 pour k = 1, 2 et 3. Le programme Stop & Go ci-joint permet de les calculer, de chercher les nombres n suivants ayant cette propriété et même de rechercher un ou des nombres n qui donnent neuf nombres premiers consécutivement. Ainsi, on obtient huit nombres premiers successifs avec les valeurs de n = 512821, 22240681, 26486461, 99597961, 593009341.

Ces recherches peuvent être longues ce qui m’a incité à développer une fonction qui permet d’interrompre l'exécution en cours avec la commande <ctrl C>, de noter la dernière valeur explorée n et de relancer ensuite une autre exécution en donnant pour valeur initiale à n la valeur obtenue précédemment.

Cet avantage essentiel de ce programme lui a donné son nom, il permet de continuer l'exploration aussi loin et aussi longtemps que l'on veut. Et rien n'empêche d'automatiser un peu plus la méthode avec un fichier qui archive la valeur finale et qui donne ensuite ultérieurement cette valeur comme valeur initiale.

GMP est une bibliothèque C++ bien connue pour traiter des entiers de taille aussi grande que nécessaire. Mais GMP est bien adaptée pour Unix ou Linux et malcommode à utiliser sous Windows. C'est pour cela qu'il existe la bibliothèque MPIR qui est une adaptation de GMP pour Windows.

L'emploi de MPIR ici est justifié par l'existence d'une fonction performante pour calculer le nombre premier qui suit un nombre donné. Il serait possible de ne pas utiliser MPIR en programmant les deux fonctions nécessaires : is_prime() et next_prime(), mais il serait difficile d'avoir autant d'efficacité.
Le programme joint et son fichier projet sont adaptés à utiliser Visual Studio et Windows.

Source : 

/****************************************************
*  Programme Stop & Go  -  @author pgl10            *
*  La formule p = k.n-k+1 peut donner une suite de  *
*  de 8 ou 9 nombres premiers pour k = 1 à 8 ou 9   *
****************************************************/

#include <iostream>
#include <cstdint>
#include <string>
#include "mpir.h"
#pragma warning(disable: 4244)
#include "mpirxx.h"
#pragma warning(default: 4244)
#include <windows.h>

bool isRunning = true;

BOOL WINAPI HandlerRoutine(DWORD dwCtrlType) {
    switch (dwCtrlType) {
        case CTRL_C_EVENT:
            isRunning = false;
            return true;
        default:
            return false;
    }
}

int main (int argc, char *argv[]) {
    mpz_class n, z;
    std::string str;
    if (argc != 2) { 
        std::cout << "nValeur initiale de n : ";
        std::cin >> str;
        n = str.c_str();
    }
    else {
        n = argv[1];
        std::cout << "nValeur initiale de n : " << n << std::endl;
    }
    std::cout << std::endl; 
    // Si n est composé on prend le nombre premier suivant
    while(mpz_probab_prime_p(n.get_mpz_t(), 10) < 1) mpz_nextprime(n.get_mpz_t(), n.get_mpz_t());
    // Pour intercepter <ctrl C>
    SetConsoleCtrlHandler(HandlerRoutine, true);
    int32_t m = 0;
    while(isRunning) {
        // Combien de fois les nombres k*n-k+1 sont-ils premiers ?
        int32_t k = 0;
        mpz_class p;
        do {
            ++k;
            p = k*n-k+1;
        }while(mpz_probab_prime_p(p.get_mpz_t(), 10) > 0);
        // Le dernier nombre p essayé n'est pas premier
        --k;
        if(k > m) {
            m = k;
            std::cout << "n = " << n << "   m = " << m << std::endl;
        }
        if(k > 7) std::cout << "n = " << n << "   k = " << k << std::endl;
        // Archivage du dernier nombre n traité
        z = n;
        // Pour passer n au nombre premier suivant
        mpz_nextprime(n.get_mpz_t(), n.get_mpz_t());
    }
    // Traitement final après <ctrl C>
    std::cout << "nValeur finale de n = " << z << std::endl;
    std::cout << "Notez le pour la prochaine fois !n" << std::endl;
    return 0 ;
}

Conclusion :

Le plus petit nombre premier n qui donne une suite de neuf nombres premiers avec la formule p = k.n-k+1 est à plusieurs milliards. On peut le trouver ainsi que les suivants.
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (pgl10)