Polynôme et nombres premiers

Télécharger le projet
Commenter

Description

Voici un programme qui comptabilise et affiche les nombres premiers produits par une formule polynômiale simple pour les petites valeurs entières successives de la variable. En effet, j'ai trouvé ou bien j'ai retrouvé un polynôme p(x) de faible degré à coefficients entiers qui donne consécutivement, pour x allant de 0 à 42, 43 nombres premiers qui sont tous positifs et tous différents. Avec ces conditions d'obtention c'est une formule dont le score est assez sûrement difficile à dépasser. Le programme joint ici en fait la vérification. Il est présenté avec quelques autres exemples. D'autres formules analogues sont disponibles sur Internet. Si on refuse de comptabiliser en tant que nombres premiers les nombres négatifs qui sont premiers en valeur absolue, il y a une petite modification très simple à faire, elle est signalée. Ce programme utilise par commodité quelques variables globales. Si l'utilisateur souhaite exclure l'emploi des variables globales il peut en faire assez facilement les changements nécessaires. Pour établir la primalité des valeurs produites par p(x) on utilise un crible d'Eratosthène spécialisé pour les nombres impairs. Il est nécessaire d'en indiquer une étendue suffisante pour couvrir toutes les valeurs produites par la formule à vérifier. Si une valeur produite est obtenue plusieurs fois, c'est affiché. En raison du codage IBM OEM de l'affichage en mode console sous Windows il convient, pour cette utilisation, de remplacer dans le source : Vérification par : V\202rification. Le fichier zip d'accompagnement contient le source, les exemples et le projet Visual Studio pour le compiler.

Source : 

 
/*****************************************************
*  Programme Ma Formule -  @author pgl10             *
*  Pour vérifier la formule p(x)=an*x^n+...+a1*x+a0  *
*  Exemple : verif ncc a4 a3 a2 a1 a0                *
*****************************************************/

#include <iostream>
#include <iomanip> 
#include <cstdint>
#include <sstream>
#include <string>
#include <vector>
#include <array>

const int64_t nccmax=34359738367;
//  nccmax est la valeur maximum de ncc 
//  ici : nccmax = (2^35)-1 
int64_t ncc;
//  limite de l'intervalle [1,ncc] de calcul du crible
std::vector<unsigned char> crible;  
//  crible[] contient les bits utiles du crible.
//  le crible ne concerne que les nombres impairs :
//  crible[0] pour 1 à 15, crible[1] pour 17 à 31, etc.

const unsigned char c0[8] = {0xFE, 0xFD, 0xFB, 0xF7, 0xEF, 0xDF, 0xBF, 0x7F};
const unsigned char c1[8] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};

//  abandon en cas d'erreur n° i
void erreur(int i) {
    std::cout << "n erreur " << i << std::endl;
    exit(EXIT_FAILURE);
}

//  Crible d'Eratosthène 
//  Uniquement les positifs impairs présents et traités dans le crible
void Eratosthene() {
    int64_t i, i2, j, s, t;
    t=1+(ncc-1)/16;
    // Initialisation de crible[] : tous les marqueurs à 1
    crible.resize(t, 0xFF);
    crible[0]= 0xFE;   // 1 n'est pas premier
    // On marque les multiples impairs de 3
    for(j=9; j<=ncc; j=j+6) crible[j>>4]=crible[j>>4]&c0[(j>>1)&7];
    i=5;
    i2=25;
    s=2;
    // On marque les multiples de i non multiples de 2 et 3
    while(i2 <= ncc) {
        if((crible[i>>4]&c1[(i/2)&7]) != 'x00') {
            for(j=i2, t=s; j<=ncc; j=j+t*i, t=6-t) {
                crible[j>>4]=crible[j>>4]&c0[(j>>1)&7];
            }
        }
        i=i+s;
        i2=i*i;
        s=6-s;
    }
}

//  Retourner true si le nombre k est premier et false si k est composé.
bool isprem(int64_t k) {  
    if(k<2 || k>ncc) return false;
    if((k&1) == 0) return k==2;
    if((crible[k>>4]&c1[(k>>1)&7]) == 'x00') return false;
    return true;
}

int main (int argc, char *argv[]) {
    if(argc < 3) erreur(1);
    // n est le degré du polynôme à vérifier
    int n = argc - 3;
    // Le vecteur a[] pour les coefficients du polynôme
    std::vector<int64_t> a(n+1, 0);
    std::istringstream iss;
    iss.str(argv[1]);
    if((iss >> ncc).fail()) erreur(1);
    if(ncc > nccmax) erreur(2);
    for(int i=0; i<=n; i++) {
        iss.clear();
        iss.str(std::string());
        iss.str(argv[n-i+2]);
        // On range a0 dans a[0], a1 dans a[1],  etc.
        if((iss >> a[i]).fail()) erreur(3);
    }
    std::cout << "n Vérification de la formule : nn p(x) = ";
    if(n  > 1) std::cout << a[n] << "*x" << n;
    if(n == 1) std::cout << a[n] << "*x";
    if(n == 0) std::cout << a[n];
    for(int i=n-1; i>=0; i--) {
        if(a[i] == 0) continue;
        if(a[i] > 0) std::cout << "+";
        if(i  > 1) std::cout << a[i] << "*x" << i;
        if(i == 1) std::cout << a[i] << "*x";
        if(i == 0) std::cout << a[i];
    }
    std::cout << "nn";
    // Crible d'Eratosthene pour les entiers impairs de 1 à ncc
    Eratosthene();
    std::array<int64_t, 65> r;
    int k=0;
    for(int x=0; x<65; x++) {
        // Calcul de p=p(x)=an*x^n+...+a1*x+a0
        int64_t p = 0;
        for(int i=n; i>=0; i--) p = p*x + a[i];
        r[x] = p;
        // Calcul de la multiplicité m de p
        int m = 1;
        for(int j=0; j<x; j++) if(r[j]==p) ++m;
        // Si on préfère exclure en tant que nombres premiers
        // les entiers négatifs quand ils sont premiers en valeur absolue
        // il suffit de mettre en commentaire l'instruction suivante :
        if(p < 0) p = -p;
        if(isprem(p)) { 
            ++k;
            // On affiche le k-ième nombre premier
            std::cout << std::setw(5) << k << "   x = " << std::setw(3) << x
                << "   p(x) = " << std::setw(12) << r[x] << "   (premier)";
            if(m > 1) std::cout << std::setw(4) << m << std::endl;
            else std::cout << std::endl;
        }
        else {
            // On affiche un nombre composé
            std::cout << "     " << "   x = " << std::setw(3) << x
                << "   p(x) = " << std::setw(12) << r[x] << "            ";
            if(m > 1) std::cout << std::setw(4) << m << std::endl;
            else std::cout << std::endl;
        }
    }
    return 0;
}

Conclusion :

Merci pour vos commentaires et remarques.
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)