Ma formule
pgl10
Messages postés
380
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
29 octobre 2023
-
2 mai 2016 à 13:56
pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 - 10 mai 2016 à 18:06
pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 - 10 mai 2016 à 18:06
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/101467-ma-formule
https://codes-sources.commentcamarche.net/source/101467-ma-formule
Modifié par pgl10 le 10/05/2016 à 18:26
Merci beaucoup pour cette liste de corrections et d'améliorations. C++ est un langage riche qui continue de s'enrichir. Parfois, on peut se demander s'il est plus facile d'apprendre les nouveautés du langage ou bien d'oublier les habitudes anciennes devenues obsolètes ! Mais quand on regarde bien ce qu'apportent les instructions C++11 c'est le plus souvent une plus grande facilité de programmation, exemples : vector, array, auto, ... Ce petit programme a permis des remarques utiles, tant mieux ! Le visiteur qui le souhaite peut réutiliser le crible d'Eratosthène optimisé pour les nombres impairs. Remerciements.
Bonjour Hbouia,
Merci pour vos remarques. Je ne connais pas Python, je m'en remets à vous à ce sujet.
Bonjour tous,
Pour utiliser le crible d'Eratosthène au delà de la limite des entiers 32 bits, il faut compiler en mode x64 et non pas en mode Win32.
9 mai 2016 à 20:28
J'aime beaucoup vos contributions sur site et c'est généreux de votre part de les partager : ça nous permet, nous lecteurs occasionnels de nous instruire et je vous en félicite particulièrement. Je suis sûr que si vos programmes son traduits en langage Python, vous aurez encore plus de lecteurs et en plus vous pourriez nous faire bénéficier de vos méthodes d'accélération des calculs pour certains algorithmes.
Exemple, tout bêtement j'ai essayé de traduire votre programme de la suite polynomiale de de degré 4 pour fournir les 43 premiers termes entiers tous premiers et distincts 2 à 2.
Comme ces des nombres sont tous relativement petits (en nombre de chiffres) :
En python et pour les non initiés, ce qui suit suffirait (Etes vous d'accord ?) :
# -*- coding: utf-8 -*- """ @author: bouia-has (Created on Mon May 09 18:45:23 2016) biblio : http://codes-sources.commentcamarche.net/source/101467-polynome-et-nombres-premiers """ import numpy as np def u(n): return 28080037+n*(-4984701+n*(331416+n*(-9777+n*108))) def estPremier(n): if n in [2,3]: return True sqrn=int(np.sqrt(n+0.1))+1 for k in range(3,sqrn,2): if n%k==0: return False return True for n in range(100): un=u(n) if not estPremier(un): break print n,' : ',un,TrueCordialement et enchanté de vous avoir lu
HB
Modifié par cptpingu le 6/05/2016 à 16:12
Quelques remarques:
Je te propose une version modifiée de ton code (en C++11, avec en bonus un petit chrono):
#include <iostream> #include <iomanip> #include <vector> #include <array> #include <cstdint> #include <cassert> #include <chrono> #define ASSERT_MSG(Cond, Msg) assert(Cond && Msg) namespace { typedef std::vector<unsigned char> crible_type; // 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 int64_t NCCMAX = 34359738367; // (2^35)-1 const unsigned char C0[] = {0xFE, 0xFD, 0xFB, 0xF7, 0xEF, 0xDF, 0xBF, 0x7F}; const unsigned char C1[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}; // Crible d'Eratosthène // Uniquement les positifs impairs présents et traités dans le crible void eratosthene(int64_t ncc, crible_type& crible) { int64_t t = 1 + (ncc - 1) / 16; crible.resize(t, 0xFF); crible[0] = 0xFE; // 1 n'est pas premier // On marque les multiples impairs de 3 for (int64_t j = 9; j <= ncc; j += 6) crible[j >> 4] = crible[j >> 4] & C0[(j >> 1) & 7]; int64_t i = 5; int64_t i2 = 25; int64_t 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]) != 0x00) { for (int64_t 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, int64_t ncc, const crible_type& crible) { if (k < 2 || k > ncc) return false; if (!(k & 1)) return k == 2; if ((crible[k >> 4] & C1[(k >> 1) & 7]) == 0x00) return false; return true; } void usage(const char** argv) { std::cout << "Usage: " << argv[0] << " <ncc> <list of nums>" << std::endl; } } //namespace int main(int argc, const char** argv) { if (argc < 3) { usage(argv); return 1; } // n est le degré du polynôme à vérifier int n = argc - 3; std::vector<int64_t> a(n + 1, 0); // limite de l'intervalle [1, ncc] de calcul du crible int64_t ncc = std::stoll(argv[1]); ASSERT_MSG(ncc > 0, "Invalid ncc!"); ASSERT_MSG(ncc <= NCCMAX, "ncc can't be > to nccmax!"); for (int i = 0; i <= n; ++i) a[i] = std::stoll(argv[n - i + 2]); std::cout << "\nVérification de la formule:\n\np(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 << "\n\n"; auto start = std::chrono::system_clock::now(); // crible d'Eratosthene pour les entiers impairs de 1 à ncc crible_type crible; eratosthene(ncc, crible); 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, ncc, crible)) { ++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; } 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::cout << "\n"; } auto end = std::chrono::system_clock::now(); const int elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); std::cout << "Elapsed time: " << elapsed << " ms" << std::endl; return 0; }