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é !    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]      
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 ;
  }
 
 
]  

En reprenant ton code (remis un poil en forme)
 

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+,

@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 !  ; y a t il de suggestions ?

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

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.

@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
   

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

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:

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+,

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 ?

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

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

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+,

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+,

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+,

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 !  
 

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

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+,

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

-->
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:

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:

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

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é.

C'est instantané en faisant retour chariot, ce qui montre l'efficacité de l'algo (assez complexe) de la librairie.
 
A+,

 
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

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.

 
A+,

 
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é!