somme entiers premiers

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : somme entiers premiers

futur_ingenieur

salut tout le monde ; je suis invité à écrire un programme qui retourne comme résultat la somme des entiers premiers infèrieurs à 2 millions !
je suis planté ! :pfff: le programme fonctionne bien et me donne la bonne réponse lorsque je le teste pour calculer la somme des entiers premiers inférieurs a 20 par exemple ! mais pour 2000000 ceci prend environ 300 secondes pour donner une fausse rèponse [s=1179908154] :cry: :cry:
pouvez vous m'aider ? je serai reconnaissant

le code que j'ai tapé en C :
[

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{ int j ;
int isprime(int n); // fonction qui retourne 1 si n est premier 0 sinon
long int s;

s=5;
for(j=5;j<2000000;j=j+2) // j=j+2 car il est inutile de tester si un nombre paire est premier
if (isprime(j))
{
s=s+j;
}
return s ;
}

int isprime(int n)
{
int p,i;
i=2;
while (((n % i) !=0) && (i<((n/2)+1)))
{
i++;
}

if ((n % i)==0) p=0 ;else p=1;

return p ;
}

]

Publicité

gilou

Modérateur
Modosaurus Rex

En reprenant ton code (remis un poil en forme)

Code :

#include <stdio.h>
#include <stdlib.h>
unsigned int increment(unsigned int n);
int main() {
unsigned long int s, t;
unsigned int i, j, k;
i = 350000;
k = 1;
s = 2 + 3; // two first primes.
t = s;
for(j = 5; j < i; j+=2) {
if (increment(j)) {
s += j;
if (t > s) {
printf("fence between %u and %u \n", k, j);
return 0;
}
t = s;
k = j;
}
}
printf("%lu\n", s);
return 0;
}
unsigned int increment(unsigned int n) {
int i;
for (i = 3; i < (n/2)+1; i+=2) {
if (!(n % i)) return 0;
}
return 1;
}

on obtient:
-> fence between 323377 and 323381
C'est a dire qu'on dépasse la valeur maximale pour un unsigned long int dès qu'on atteint le nombre premier 323381
(Bon, si tu as des extensions de compilateur, c'est à tester avec des entiers sur 64 bits)

A+,

---------------
There's more than what can be linked! -- Le capitaine qui ne veut pas obéir à la carte finira par obéir aux récifs. -- Il ne faut plus dire Sarkozy, mais Sarkozon -- (╯°□°)╯︵ ┻━┻

futur_ingenieur

@gilou merci
mais une variable int est dans l'intervalle [-2 147 483 648 , 2 147 483 647 ] (source : tutoriel de site du zero)
en plus : le programme retourne comme valeur :[s=1179908154] !!
ou bien je n'ai pas bien compris ce que vous venez de dire ! :pfff: ; y a t il de suggestions ?

Message cité 1 fois

futur_ingenieur

c'est maintenant que je viends de te comprendre ! donc j'ai sommé les entiers premiers inferieurs à 323381 ?
que je devais faire ?

Terminapor

I'll see you rise.

Quand tu précise unsigned, ça va de 0 à FFFFFFFF, soit ~4 000 000 000
En gros, il veut dire que le nombre premier qui vient après 323 381 est trop grand pour être stocké dans un int
Ton soucis vient de ça, un overflow.

---------------
Perhaps you don't deserve to breathe

futur_ingenieur

@terminapor ! merci mais il y a une contradiction dans ce que tu dit ! comment 323 381 ne peut pas étre stocké dans un int o.O pourtant le resultat s est est int : s=1179908154

futur_ingenieur

gràce à MAPLE ; le nombre premier qui suit 323 381 est 323 383 encore plus petit que s=1179908154 .

gilou

Modérateur
Modosaurus Rex

Ce qu'on te dit, c'est que ta somme dépasse la bonne valeur admissible pour le nombre premier indiqué, et donc qu'ensuite la valeur n'est plus bonne.
pour le nombre premier 323381, on a: 27875e nombre premier, la somme à ce point (323381 pas inclus dans la somme) est 4294841976
pour le nombre premier 323383, on a: 27876e nombre premier, la somme à ce point est 4295165357 (4295165357 - 4294841976 = 323381)
Un unsigned long (sur une machine en 32 bits) va de 0 à 4294967295, et on voit bien que 4294967295 se situe entre 4294841976 et 4295165357.

Tiens, si ça t'intéresse, une solution possible:

Code :

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
int main() {
int i, j;
mpz_t sum;
unsigned int primes[150000]; // 148933 primes in fact
unsigned int nbprimes = 0;
primes[nbprimes++] = 2;
primes[nbprimes++] = 3;
for (i = 5; i < 2000000; i+=2) {
for (j = 0; j < nbprimes; ++j) {
if (!(i%primes[j])) break;
}
if (j == nbprimes) {
primes[nbprimes++] = i;
}
}
printf("%d\n", nbprimes);
mpz_init(sum);
for (j = 0; j < nbprimes; ++j) {
mpz_add_ui(sum, sum, primes[j]);
}
mpz_out_str(stdout, 10, sum);
mpz_clear(sum);
return 0;
}

Retourne le nombre de nombre premiers inférieurs a 2000000 et leur somme
148933
142913828922
J'ai utilisé la librairie libgmp de gnu pour pouvoir sommer de grand nombres et les afficher [la downloader, compiler, tester, installer et lire succintement la doc pour pondre cet exemple m'a pris un peu plus de 30mn].
Au départ, je construit une table à 150 000 entrées (j'ai lancé le programme avec un garde fou pour ne pas dépasser le nb d'entrées du tableau primes pour évaluer le nb d'entrée nécessaires, par approximations), et l'algo est simple: je met pas a pas les nombres premiers dans ma table, et un nombre (impair) est premier (et ajouté à la table) s'il n'est pas divisible par une des valeurs déjà existantes dans la table. Ensuite, je n'ai plus qu'à sommer les valeurs contenues dans la table.

Noter aussi que si vous êtes en C++ et non en C, le type unsigned long long int varie de 0 à 18446744073709551615 et est largement suffisant, sans avoir besoin de faire appel à une librairie spécialisée (et si vous êtes en 64 bits, un unsigned long int devrait avoir cette même borne maximum et convenir).
A+,

Message édité par gilou le 01-04-2012 à 11:04:12

futur_ingenieur

merci gilou mais ce qui m'intèrsse vraiment est de savoir comment resoudre ce problème ; j'ai essayé d'ajouter la bibliothèque #include <gmp.h>
mais en vain mon compilateur ne vient pas de l'accepter il me signale un erreur au niveau de cette bibliothèque ! je travaille avec code bloks sous windows (64-bits) ! y a t il une bibliothèque qui pourrait faire la meme chose ?
en d'autres mots ! est ce que mon programme est non corrigeable ?

futur_ingenieur

comme je ne viens pas d'executer ton programe sur ma machine ; j'aime bien savoir le temps d'execution + la capacitè de la RAM de ta machine !
et merci encore

Message cité 1 fois

Publicité

gilou

Modérateur
Modosaurus Rex

Citation :

je travaille avec code bloks sous windows (64-bits)

Eh bien alors un unsigned long est assez grand pour le résultat dans votre cas (si vous compilez du code 64 bits).
Dans ce cas la

Code :

#include <stdio.h>
#include <stdlib.h>
int main() {
int i, j;
unsigned long int sum;
unsigned int primes[150000]; // 148933 primes in fact
unsigned int nbprimes = 0;
primes[nbprimes++] = 2;
primes[nbprimes++] = 3;
for (i = 5; i < 2000000; i+=2) {
for (j = 0; j < nbprimes; ++j) {
if (!(i%primes[j])) break;
}
if (j == nbprimes) {
primes[nbprimes++] = i;
}
}
printf("%d\n", nbprimes);
sum = 0;
for (j = 0; j < nbprimes; ++j) {
sum += primes[j];
}
printf("somme: %lu\n", sum);
return 0;
}

ceci devrait marcher, et si ce n'est pas le cas, c'est que vous ne générez pas du code 64 bits (code block en 32 bits?)
A+,

Message édité par gilou le 01-04-2012 à 02:27:38

gilou

Modérateur
Modosaurus Rex

futur_ingenieur a écrit :

comme je ne viens pas d'executer ton programe sur ma machine ; j'aime bien savoir le temps d'execution + la capacitè de la RAM de ta machine !
et merci encore

C'est une vieille bécane pourrie et antique sous XP avec 2Go de Ram et un Pentium 4 3Ghz (valeur 40€ neuf, c'est dire son antiquité).
L’exécution est moins de 5mn pour le programme avec libgmp. Et de l'ordre de 5mn pour l'autre, limité à 1000000 (comme l'algo est exponentiel, j'ose pas imaginer le temps que ça prend pour 2000000)
A+,

gilou

Modérateur
Modosaurus Rex

Dans votre code initial, il y a ceci:
if ((n % i)==0) p=0 ;else p=1;
au lieu de
if ((n % i)==0) p=0 else p=1;
et ça peut être source de pb.

A+,

futur_ingenieur

un grand merci ! gilou tu es très serviable ! que dieu te bènisse avec un HP 500 GO / 4 GO /i7

j'ai essayé avec unsigned long ! mais en vain : le méme rèsultat , je vais résoudre ce problème avec maple ou matlab ! j'en ai marre de ce C !

Message cité 1 fois

gilou

Modérateur
Modosaurus Rex

futur_ingenieur a écrit :

@gilou merci
mais une variable int est dans l'intervalle [-2 147 483 648 , 2 147 483 647 ] (source : tutoriel de site du zero)
en plus : le programme retourne comme valeur :[s=1179908154] !!
ou bien je n'ai pas bien compris ce que vous venez de dire ! :pfff: ; y a t il de suggestions ?

Ma signature exprime mon opinion à ce sujet.
A+,

gilou

Modérateur
Modosaurus Rex

futur_ingenieur a écrit :

Pour faire de gros calculs numériques, il faut utiliser une librairie appropriée comme libgmp ou similaire, ce qui est assez normal avec les langages de programmation compilés.

Comme j'ai dit, ça a du prendre 30 mn a récupérer, compiler, installer, utiliser:
1) dowloader ça sur http://gmplib.org/
2) desarchiver l'archive sur la racine d'un disque (C: par exemple ca va creer un répertoire C:\gmp-5.0.4)
3) lancer le shell MSYS de MINGW (ca doit être un package optionnel de Code blocks)
4) taper dans le shell: "cd /c/gmp-5.0.4" (si on a désarchivé dans C:\gmp-5.0.4)
5) taper ./configure (j'ai du stopper temporairement mon antivirus à ce stade, il voit des trojans dans les a.exe ce qui est totallement faux)
6) quand c'est configurer taper "make"
7) après 10 a 15 mn de compil, taper "make check" pour voir si les tests passent
8) si OK taper "make install"
9) taper exit pour quitter le shell MSYS de MINGW
10) virer le répertoire C:\gmp-5.0.4, inutile maintenant
11) aller dans le répertoire msys\1.0\local de Msys (dans MINGW chez moi), copier le gmp.h du répertoire include dans le repertoire include de MINGW, les deux librairies (libgmp.a et libgmp.la) du repertoire lib dans le repertoire lib de MINGW et ça roule [ça marche peurt être sans dans l'environnement de code blocks si les paths sont bien configurés]
12) ajouter la librairie libgmp.a a celle avec lesquelles on linke (option dans le projet code block)
Perso, j'utilise pas code block, je fais ça a la main en ligne de commande, pour juste un fichier, je vais plus vite.
A+,

Message édité par gilou le 01-04-2012 à 02:53:23

gilou

Modérateur
Modosaurus Rex

Bon sinon, comme j'avais dit, on peut le faire en C++ qui a des unsigned long long ints.
Je transpose le code:

Code :

#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
int main() {
vector<unsigned int> primes;
vector<unsigned int>::iterator it;
unsigned long long int sum = 0;
primes.reserve(150000); // 148933 primes in fact
primes.push_back(2);
primes.push_back(3);
for (unsigned int i = 5; i < 2000000; i+=2) {
for (it = primes.begin(); it < primes.end(); it++) {
if (!(i%(*it))) break;
}
if (it == primes.end()) {
primes.push_back(i);
}
}
for (it = primes.begin(); it < primes.end(); it++) {
sum += *it;
}
cout << "Nb of prime numbers: " << primes.size() << endl;
cout << "Sum of prime numbers: " << sum << endl;
return 0;
}

-->
Nb of prime numbers: 148933
Sum of prime numbers: 142913828922

Bon par contre, les vectors, c'est peut être pas une bonne idée, parce que j'ai un temps d’exécution de l'ordre de 2 fois celui en C.

Par contre ceci:

Code :

#include <iostream>
using std::cout;
using std::endl;
int main() {
unsigned int primes[150000];
unsigned int nbprimes = 0;
unsigned long long int sum = 0;
unsigned int i, j;
primes[nbprimes++] = 2;
primes[nbprimes++] = 3;
for (i = 5; i < 2000000; i+=2) {
for (j = 0; j < nbprimes; ++j) {
if (!(i%(primes[j]))) break;
}
if (j == nbprimes) {
primes[nbprimes++] = i;
}
}
for (j = 0; j < nbprimes; ++j) {
sum += primes[j];
}
cout << "Nb of prime numbers: " << nbprimes << endl;
cout << "Sum of prime numbers: " << sum << endl;
return 0;
}

est plus rapide d'1/3 que le programme C équivalent.

Ce programme ci, qui utilise les conteneurs modernes, a un temps d'exécution du même ordre que le précédent:

Code :

#include <iostream>
#include <algorithm>
#include <array>
using std::cout;
using std::endl;
using std::array;
using std::fill;
int main() {
array<unsigned int, 150000> primes = {2, 3}; // 148933 primes in fact
fill(primes.begin()+2, primes.end(), 0); // fill other places with 0
array<unsigned int, 150000>::iterator it;
unsigned long long int sum = 0;
for (unsigned int i = 5; i < 2000000; i+=2) {
for (it = primes.begin(); *it; it++) {
if (!(i%(*it))) break;
}
if (!*it) {
*it = i;
}
}
for (it = primes.begin(); *it; it++) {
sum += *it;
}
for (it = primes.end(); !*it; it--);
it++; // first position not filled with a prime
cout << "Nb of prime numbers: " << (it - primes.begin()) << endl;
cout << "Sum of prime numbers: " << sum << endl;
return 0;
}

à compiler avec le flag -std=c++0x
A+,

Message édité par gilou le 01-04-2012 à 14:33:15

gilou

Modérateur
Modosaurus Rex

Ensuite, si tu veux une implémentation efficace, tu vas voir ici: http://cr.yp.to/primegen.html
chez moi, primes.exe trouve et imprime (c'est ce qui prends le plus de temps) les nbs premiers entre 1 et 2000000 en moins de 2mn.

Et en utilisant cette librairie primegen
En compilant l'exemple qui suit avec gcc -std=c99 -o sump.exe sump.c primegen.a (et avec primegen.h, uint32.h et uint64.h accessibles a la compilation)
Le flag -std=c99 est important, sinon, les unsigned long long int ne marcheront pas correctement et le résultat sera erroné.

Code :

#include <stdio.h>
#include "primegen.h"
int main() {
primegen pg;
unsigned int nbprimes = 0;
unsigned long long int sum = 0;
primegen_init(&pg);
primegen_skipto(&pg, 2);
while (primegen_peek(&pg) < 2000000) {
sum += primegen_next(&pg);
++nbprimes
}
printf("nb of primes %u\n", nbprimes);
printf("sum of primes %llu", sum);
return 0;
}

C:\clang>sump
nb of primes 148933
sum of primes 142913828922

C'est instantané [:darkmavis tt] en faisant retour chariot, ce qui montre l'efficacité de l'algo (assez complexe) de la librairie.

A+,

Message cité 1 fois
Message édité par gilou le 01-04-2012 à 15:54:19

edwoud

⭐ shériff de l'espace

gilou a écrit :

C:\clang>sump
nb of primes 148933
sum of primes 142913828922

C'est instantané [:darkmavis tt] en faisant retour chariot, ce qui montre l'efficacité de l'algo (assez complexe) de la librairie.

Il est probable qu'une grosse partie des nombres premiers soient stockés en interne. Ça permet aussi d'optimiser la recherche (au lieu de tester les nombres impaires, on ne teste le modulo qu'avec les nombres premiers, et ça tombe bien si on les connait déjà). Un peu comme une bibliothèque d'ouverture aux échecs

gilou

Modérateur
Modosaurus Rex

Citation :

Il est probable qu'une grosse partie des nombres premiers soient stockés en interne.

Au vu du source (un seul fichier, primegen.c) , non (si tu entends par la qu'il y a une table de nb premiers précalculée dans le source).
Tu as quelques tables de quadruplet (la plus grosse en a 128) et une structure avec de l'ordre de 30 000 uint64, mais ça a l'air de fonctionner essentiellement avec un algo assez fortement optimisé basé sur le reste modulo 60 du nombre.

Citation :

primegen is a small, fast library to generate prime numbers in order. It generates the 50847534 primes up to 1 000 000 000 in just 8 seconds on a Pentium II-350; it prints them in decimal in just 35 seconds.
primegen can generate primes up to 10^15, although it is not optimized for primes past 32 bits. It uses the Sieve of Atkin instead of the traditional Sieve of Eratosthenes.

Citation :

Sieve of Atkin
From Wikipedia, the free encyclopedia

In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. It is an optimized version of the ancient sieve of Eratosthenes which does some preliminary work and then marks off multiples of the square of each prime, rather than multiples of the prime itself. It was created by A. O. L. Atkin and Daniel J. Bernstein.

In the algorithm:

All remainders are modulo-sixty remainders (divide the number by sixty and return the remainder).
All numbers, including x and y, are whole numbers (positive integers).
Flipping an entry in the sieve list means to change the marking (prime or nonprime) to the opposite marking.
Create a results list, filled with 2, 3, and 5.
Create a sieve list with an entry for each positive integer; all entries of this list should initially be marked nonprime.
For each entry number n in the sieve list, with modulo-sixty remainder r :
If r is 1, 13, 17, 29, 37, 41, 49, or 53, flip the entry for each possible solution to 4x2 + y2 = n.
If r is 7, 19, 31, or 43, flip the entry for each possible solution to 3x2 + y2 = n.
If r is 11, 23, 47, or 59, flip the entry for each possible solution to 3x2 − y2 = n when x > y.
If r is something else, ignore it completely.
Start with the lowest number in the sieve list.
Take the next number in the sieve list still marked prime.
Include the number in the results list.
Square the number and mark all multiples of that square as nonprime.
Repeat steps five through eight.
This results in numbers with an odd number of solutions to the corresponding equation being prime, and an even number being nonprime.

Explanation

The algorithm completely ignores any numbers divisible by two, three, or five. All numbers with an even modulo-sixty remainder are divisible by two and not prime. All numbers with modulo-sixty remainder divisible by three are also divisible by three and not prime. All numbers with modulo-sixty remainder divisible by five are divisible by five and not prime. All these remainders are ignored.
All numbers with modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-four remainder of 1. These numbers are prime if and only if the number of solutions to 4x2 + y2 = n is odd and the number is squarefree (proven as a theorem).
All numbers with modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime if and only if the number of solutions to 3x2 + y2 = n is odd and the number is squarefree (proven as a theorem).
All numbers with modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime if and only if the number of solutions to 3x2 − y2 = n is odd and the number is squarefree (proven as a theorem 6.3).
None of the potential primes are divisible by 2, 3, or 5, so they can't be divisible by their squares. This is why squarefree checks don't include 22, 32, and 52.

Computational complexity

This sieve computes primes up to N using O(N/log log N) operations with only N1/2 + o(1) bits of memory. That is a little better than the sieve of Eratosthenes which uses o(N) operations and O(N1/2(log log N)/log N) bits of memory

A+,

Message cité 1 fois
Message édité par gilou le 02-04-2012 à 14:15:29

edwoud

⭐ shériff de l'espace

gilou a écrit :

Citation :

Il est probable qu'une grosse partie des nombres premiers soient stockés en interne.

Au vu du source (un seul fichier, primegen.c) , non (si tu entends par la qu'il y a une table de nb premiers précalculée dans le source).

En fait, je pensais à un stockage séquentiel, au fur et à mesure des appels à la fonction primegen_next. Mais l'algorithme d'atkin et Bernstein est bluffant de simplicité!

Publicité

FORUM HardWare.fr

Programmation

somme entiers premiers

Sujets relatifs
pointeur de tableau 2D d'entiers...	somme d'heures en PHP
editer JTable contenant des entiers	probleme excel vba somme
Effectuer une somme avec condition sous excel	Calculer somme des champs d'un formulaire
[resolu] faire un max d'une somme : j'y arrive pas !	somme datetime
Comment générer tous les entiers d'une borne (Le code est-il correct?)	Count et somme
Plus de sujets relatifs à : somme entiers premiers

Page générée en 0.159 secondes