Algorithme test de primalité

Trouvé un algorithme qui soit le plus optimisé possible pour faire un teste de primalité (vérifier si un nombre est premier)

a marqué ce sujet comme résolu.

Bonjour, je n’ai pas l’habitude de vraiment publier sur le site… Je fais un peu de programmation et j’aime les algorithmes, et pour tester un peu j’ai décidé de faire un algorithme qui peut vérifier si un nombre est premier 🤔… Mais de la façon la plus optimisé possible !

Du coup je cherche de potentiel optimisations et bien sûr avec les explications qui vont avec (ou les sources :) )

Pour l’instant j’ai trouvé celles-ci :

  • Ignorer les nombres paires
  • Vérifier avec tout les nombres jusqu’à la racine du nombre à vérifier

En C++ ça donne ça :

#include <iostream>
#include <cstdint>
#include <cmath>

bool IsPrime(std::uintmax_t n) {

    // Exceptions
    if (n == 2) return true;

    if (!(n & 1)) return false; // Pariété (ne doit pas être paire)
    if (n < 2) return false; // Trop petit

    // Boucle (brut force)
    for (std::uintmax_t i{3}; i <= sqrt(n); i += 2) {

        if (n%i == 0) return false;

    }

    return true;

}

int main() {

    for (std::size_t i{0}; i < 100; i++) {

        if (IsPrime(i)) std::cout << i << std::endl;

    }

    std::cin.get();

    return 0;

}

Merci beaucoup :) !

+0 -0

Du coup je cherche de potentiel optimisations et bien sûr avec les explications qui vont avec (ou les sources :) )

Olive :)

Salut,

Pas forcément une optimisation… enfin ça dépendra de ton utilisation. Ça peut valoir le coup dans des cas comme ici où tu testes les primalité des premiers entiers naturels.

Ça consisterait à mettre en cache les résultats précédents et ainsi ne pas tester les diviseurs que tu sais ne pas être premiers. Ainsi, pour calculer isPrime(97) tu ne testerais les divisions que par 3, 5 et 7.

+1 -0

Sans mise en cache, mais dans la même idée, il est aussi possible de stocker les plus petits nombres premiers. Ça permet d’éliminer très rapidement les nombres ayant de petits diviseurs, et donc une grande quantité de nombres non-premiers. Pour précalculer une liste, la crible d’Ératosthène est une piste.

Une autre idée sympa à explorer, c’est une généralisation de la distinction pair/impair, avec le reste de la division euclidienne. Par exemple, les nombres de la forme 3n ne peuvent pas être premiers (à part 3 lui-même), mais 3n+1 ou 3n+2 possiblement. Comme ça, on teste moins de nombres.

Ensuite, il y a des algorithmes différents et théoriquement plus efficaces, mais plus compliqués et qui n’ont pas forcément d’intérêt pratique pour toi.

+1 -0

La feinte classique que je connais c’est effectivement que seuls 6k+1 et 6k+5 (/-1) peuvent être premiers lors du parcours pour remplir le tableau des nombres premiers.

Si mes souvenir sont bons, c’est une des principales approches d’un outil en vogue sur le sujet: https://github.com/kimwalisch/primesieve

PS: Appeler sqrt() à chaque itération sera inefficace. On testera plutôt i*i

PPS: !(n & 1), c’est vrai, mais c’est de l’obfuscation, et en plus le compilo produira le même assembleur sur i % 2. Cela fera peut être la différence avec un langage interprété, ou un compilé d’il y a 25+ans, aujourd’hui, ça ne change rien.

+1 -0

Bonjour, ça va dépendre aussi de ce que tu entends par optimisation. Tu peux optimiser le code en gardant l’algorithme. Là je ne pense que tu gagneras quoi que ce soit.

Tu peux également modifier légèrement l’algorithme. Comme le propose @entwanne, tu peux considérer utiliser une liste de « petits nombres premiers ». Par exemple avec la liste des 102 premiers nombres premiers tu peux aisément tester les nombres jusqu’à 310273 (le premier nombre premier plus grand que 557×557=310249, 557 étant le 102ème nombre premier).

Tu peux aussi étendre les tests de divisibilité en te restreignant aux nombres multiples de 6 ± 1. En effet, quand tu testes uniquement les nombres impairs tu élimines ceux de la forme 2k+22k+2 car il sont des multiples de 2, mais tu dois faire un test particulier pour 2.

En poussant le raisonnement plus loin on pourrait filtrer les multiples de 2 ou 3. On peut faire cela en considérant le reste de la division par 6, pour les restes 0,2,3,4 tu sais que tu as à faire à un multiple de 2 ou 3, il ne reste plus qu’à tester les nombres dont le reste vaut 1 ou 5 (de manière équivalente, -1). Au lieu de tester un nombre sur deux (50%) tu en testes 2 sur 6 (33%) avec un test supplémentaire pour 3 en plus.

En peut aller encore plus loin en utilisant 2×3×5=30 qui est premier avec 1,7,11,13,17,19,23 et 29. Tu ne testerais plus que 7 nombres sur 30 (23.4%) au détriment d’avoir des tests particuliers pour 2,3 et 5. Ainsi de suite en considérant 2×3×5×7=210, 2×3×5×7×11=2310, … Mais c’est de moins en moins « rentable » dans le sens où le gain est de moins en moins important.

Ensuite tu peux également implémenter un algorithme que tu ne comprends pas forcément mais qui est simple, comme un test de miller-rabin. Si tu travailles sur des nombres < 264 alors tu te restreindre à faire 12 tests dans les bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, et 37 pour rendre l’algo déterministe.

Tu peux également mixer tout ça …

+1 -0

Sans mise en cache, mais dans la même idée, il est aussi possible de stocker les plus petits nombres premiers. Ça permet d’éliminer très rapidement les nombres ayant de petits diviseurs, et donc une grande quantité de nombres non-premiers. Pour précalculer une liste, la crible d’Ératosthène est une piste.

C’est je trouve conceptuellement plus simple (en plus d’être plus générique) d’avoir un tableau ou une liste potentiellement infinis des nombre premiers rencontrés et de ne jouer qu’avec eux.

PS: Appeler sqrt() à chaque itération sera inefficace. On testera plutôt i*i

Ou plus simple, tu calcules sqrt() une fois au début, tu stockes le résultat et tu compares avec i directement. Notons qu’un compilateur fait probablement l’optimisation par défaut car n (et donc sqrt(n) est invariant dans la boucle.

+1 -0

Sans mise en cache, mais dans la même idée, il est aussi possible de stocker les plus petits nombres premiers. Ça permet d’éliminer très rapidement les nombres ayant de petits diviseurs, et donc une grande quantité de nombres non-premiers. Pour précalculer une liste, la crible d’Ératosthène est une piste.

C’est je trouve conceptuellement plus simple (en plus d’être plus générique) d’avoir un tableau ou une liste potentiellement infinis des nombre premiers rencontrés et de ne jouer qu’avec eux.

PS: Appeler sqrt() à chaque itération sera inefficace. On testera plutôt i*i

Ou plus simple, tu calcules sqrt() une fois au début, tu stockes le résultat et tu compares avec i directement. Notons qu’un compilateur fait probablement l’optimisation par défaut car n (et donc sqrt(n) est invariant dans la boucle.

Renault

Je crois que pour ça il faudrait mettre l’argument n en const dans la fonction 🤔

+0 -0

Sans mise en cache, mais dans la même idée, il est aussi possible de stocker les plus petits nombres premiers. Ça permet d’éliminer très rapidement les nombres ayant de petits diviseurs, et donc une grande quantité de nombres non-premiers. Pour précalculer une liste, la crible d’Ératosthène est une piste.

C’est je trouve conceptuellement plus simple (en plus d’être plus générique) d’avoir un tableau ou une liste potentiellement infinis des nombre premiers rencontrés et de ne jouer qu’avec eux.

PS: Appeler sqrt() à chaque itération sera inefficace. On testera plutôt i*i

Ou plus simple, tu calcules sqrt() une fois au début, tu stockes le résultat et tu compares avec i directement. Notons qu’un compilateur fait probablement l’optimisation par défaut car n (et donc sqrt(n) est invariant dans la boucle.

Renault

Je crois que pour ça il faudrait mettre l’argument n en const dans la fonction 🤔

Olive :)

Les compilateurs sont malins, même si un const n’est aps renseigné, ils peuvent voir s’il sera changé dans le corps de la fonction ou pas et ajuster le comportement. Mais c’est une bonne idée de l’ajouter, cela ajoute des garanties au compilateur et à toi même : si tu essayes de changer la valeur de n ton code ne compilera pas ce qui évitera un bogue peut être gênant.

+1 -0

Ou plus simple, tu calcules sqrt() une fois au début, tu stockes le résultat et tu compares avec i directement. Notons qu’un compilateur fait probablement l’optimisation par défaut car n (et donc sqrt(n) est invariant dans la boucle.

Renault

Il semblerait que non. En plus, il faudra le recaster nous même en int pour éviter des conversions inutiles à la volée.

EDIT: J’avais oublié le lien https://godbolt.org/z/6aaYGe7so

+0 -0

Une mise à jour de l’algorithme depuis avec comme ajout :

  • Base de données des premiers nombres premiers (de 0 à 4000) pour faciliter les premiers diviseurs (idée de @entwanne puis modification sans cache de @Aabu)
  • Base de données en cache contenant les nombres déjà testés
  • Application des corrections proposées par @lmghs
  • En plus de vérifier la pariété on généralise pour les 12 premiers nombres premiers (proposé par @Aabu et @ludox)
  • En me renseignant j’ai appris qu’un nombre premier ne pouvait pas être un carré parfait (un carré parfait est un nombre dont la racine est un nombre entier)

J’ai apportées les modifications au code et voilà :

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdint>
#include <limits>
#include <vector>
#include <cmath>

namespace Data_Base {

    // de 1 à 4000
    const std::vector<std::int16_t> smallPrimes {
        
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
        101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
        199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
        317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439,
        443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571,
        577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
        701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
        839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977,
        983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093,
        1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229,
        1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367,
        1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489,
        1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613,
        1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753,
        1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901,
        1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039,
        2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179,
        2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333,
        2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447,
        2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621,
        2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731,
        2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879,
        2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037,
        3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203,
        3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343,
        3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499,
        3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623,
        3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769,
        3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 
        3923, 3929, 3931, 3943, 3947, 3967, 3989
    
    };

    // Cache (reset à chaque démarrage)
    std::unordered_map<std::intmax_t, bool> primes;

}

bool IsPrime(const std::uintmax_t n) {

    if (Data_Base::primes.find(n) != Data_Base::primes.cend()) return Data_Base::primes[n];

    // Exceptions
    if (n < 2) {
        
        Data_Base::primes[n] = false;
        return false; // Trop petit

    }

    if (n == 2) {
        
        Data_Base::primes[n] = true;
        return true;

    }

    if (std::sqrt(n) == static_cast<int>(std::sqrt(n))) {
        
        Data_Base::primes[n] = false;
        return false; // Un nombre premier ne peut pas avoir de racine entière

    }

    if (n%2 == 0 ||
        n%3 == 0 ||
        n%5 == 0 ||
        n%7 == 0 ||
        n%11 == 0 ||
        n%13 == 0 ||
        n%17 == 0 ||
        n%19 == 0 ||
        n%23 == 0 ||
        n%29 == 0 ||
        n%31 == 0 ||
        n%37 == 0

    ) {
            
        Data_Base::primes[n] = false;
        return false;

    }

    if (n <= Data_Base::smallPrimes.back()) {
        
        return Data_Base::primes[n] = std::find(Data_Base::smallPrimes.cbegin(), Data_Base::smallPrimes.cend(), n) != Data_Base::smallPrimes.cend();

    }

    // Boucle (brut force)
    if (Data_Base::smallPrimes.back()*Data_Base::smallPrimes.back() >= n) {

        for (std::size_t i{0}; i < Data_Base::smallPrimes.size(); i++) {

            if (n%Data_Base::smallPrimes[i] == 0) {
                
                Data_Base::primes[n] = false;
                return false;

            }

        }

    } else {

        for (std::uintmax_t i{static_cast<std::uintmax_t>(Data_Base::smallPrimes.back())}; i*i <= n; i += 2) {

            if (n%i == 0) {
                
                Data_Base::primes[n] = false;
                return false;

            }

        }

    }

    Data_Base::primes[n] = true;
    return true;

}

int main() {

    for (std::uint32_t i{0}; i < 2000000; i++) {

        if (IsPrime(i)) std::cout << i << std::endl;

    }

    std::cin.get();

    return 0;

}
+0 -0

C’est pas un peu de la triche de donner une liste de nombres premiers jusqu’à sqrt(n)? L’algorithme n’a aucun intérêt si on admet cette liste pour tout n

Holosmos

Je fais ça juste pour les premiers nombres, afin d’éviter de diviser par des nombres "inutiles" (qui ne sont pas premiers) mais cette liste est bien finit (et elle doit l’être) ce qui fait que si n est trop grand on appliquera la méthode "brut force"… Donc pas applicable pour tout n

+0 -0

C’est pas un peu de la triche de donner une liste de nombres premiers jusqu’à sqrt(n)? L’algorithme n’a aucun intérêt si on admet cette liste pour tout n

Holosmos

Tous les algorithmes n’ont pas le même champ d’application. Si ton objectif est de faire un algo avec des connaissances préalables minimales, c’est différent de résoudre un problème où tu dois tester rapidement la primalité de relativement petits nombres avec un compromis temps/mémoire et où avoir une liste est pragmatique.

+1 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte