Frage zu Overflowproblem bei bildung von Summe aus Primzahle
Verfasst: Mo Dez 21, 2015 12:39 am
Hallo erstmal,
nachdem ich letzten Sonntag (also mittlerweile von genau 8 Tagen) mit dem C Programmieren angefangen habe, bin ich jetzt das erste mal mit einem Programm an einem Punkt an dem ich durch googlen und selber daran rumbasteln leider nichtmehr weiter komme.
Bevor ich auf das Problem eingehe, möchte ich mich noch kurz ganz herzlich bei Xin für die Tutorials bedanken! Ich bin jetzt bei den letzten C Kapiteln angelangt und habe dabei extrem viel gelernt, dankeschön für die Mühe!
Nun zu meinem Problem
Es handelt sich um Euler Problen Nr.10 von projecteuler.net (https://projecteuler.net/problem=10).
Dabei geht es darum die Summe aller Primzahlen unter 2 Millionen zu berechnen. Dazu habe ich Code weiterverwendet den ich bereits geschrieben hatte um die n-te Primzahl zu berechnen und auszugeben. Da ich die Primzahlen dabei sowieso alle bis zur n-ten Primzahl berechnen muss und in einem Array speichere, habe ich das Array einfach in die main-funktion gepackt und in meiner Funktion zur berechnung der ersten n Primzahlen führe ich dann nurnoch einen Call-by-Pointer auf das Array aus, in dem später alle n angeforderten Primzahlen stehen.
Der algorithmus zur Ermittlung der Primzahlen ist bis weit über 2Mio hinaus stabil, das habe ich mehrfach geprüft.
Weiter geht es dann mit der Funktion zur Addition der ersten n Primzahlen. Die if-Bedingung ist hier eingebaut um eben genau mein Problem zu lösen, ist zwar nicht elegant... aber schnell implementiert
.
Das Vorgehen sieht dann so aus: Ich starte das Programm mit Übergabeparameter n = 150000 ... und bekomme als Summe 1709600813, was leider nicht stimmt. Ich bin mir allerdings sehr sicher, dass der Algorithmus stimmen sollte denn für die Summe aller Primzahlen unter 100000 liefert er das richtige Ergebnis.
Meine Vermutung (gestützt durch stundenlanges googlen) geht dahin, dass irgendwo ein overflow passiert, aber soweit ich das sehe sollte unsigned long long int für das erwartete Ergebnis 142913828922 locker ausreichen.
Daher meine Frage: Was übersehe ich? Wo kommt er weshalb nicht hin mit dem Datentyp?
gruß
nachdem ich letzten Sonntag (also mittlerweile von genau 8 Tagen) mit dem C Programmieren angefangen habe, bin ich jetzt das erste mal mit einem Programm an einem Punkt an dem ich durch googlen und selber daran rumbasteln leider nichtmehr weiter komme.
Bevor ich auf das Problem eingehe, möchte ich mich noch kurz ganz herzlich bei Xin für die Tutorials bedanken! Ich bin jetzt bei den letzten C Kapiteln angelangt und habe dabei extrem viel gelernt, dankeschön für die Mühe!
Nun zu meinem Problem
Es handelt sich um Euler Problen Nr.10 von projecteuler.net (https://projecteuler.net/problem=10).
Dabei geht es darum die Summe aller Primzahlen unter 2 Millionen zu berechnen. Dazu habe ich Code weiterverwendet den ich bereits geschrieben hatte um die n-te Primzahl zu berechnen und auszugeben. Da ich die Primzahlen dabei sowieso alle bis zur n-ten Primzahl berechnen muss und in einem Array speichere, habe ich das Array einfach in die main-funktion gepackt und in meiner Funktion zur berechnung der ersten n Primzahlen führe ich dann nurnoch einen Call-by-Pointer auf das Array aus, in dem später alle n angeforderten Primzahlen stehen.
Der algorithmus zur Ermittlung der Primzahlen ist bis weit über 2Mio hinaus stabil, das habe ich mehrfach geprüft.
Code: Alles auswählen
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <unistd.h>
int primzahl(int n, long long unsigned int *pz) //Funktion zur Berechnung der ersten n Primzahlen
{
pz[0]=1; pz[1]=2;
int m = 2; // anzahl der bekannten Primzahlen
long long unsigned int p = 3; // erste zahl die Untersucht wird
while(m <= n)
{
int a = 1;
for(int i = 1 ; i < m ; i++) //prüfe ob p durch irgendeine Primzahl teilbar ist, falls ja setzte p = p + 1 und springe an den Anfang
{
if(p % pz[i] != 0)
{
a = a + 1;
}
else
{
p = p + 1;
break;
}
}
if (a == m)
{
printf("Die %d te Primzahl lautet %llu\n", m, p);
pz[m] = p;
p = p + 1;
m = m + 1;
}
}
return pz[n];
}
int long long unsigned addition(int n , long long unsigned int *pz) //Funktion zur Addition der ersten n Primzahlen
{
int long long unsigned sum = 0;
for ( int i = 1 ; i <= n ; i++)
{
if( pz[i] < 200000 )
sum = sum + pz[i];
else
continue;
}
return sum;
}
int main (int argc, char *argv[])
{
int n = atoi(argv[1]);
long long unsigned int pz[n]; // das Array in dem die Primzahlen gespeichert werden
for(int i = 0; i < n ; i++)
pz[i] = 0;
primzahl(n , pz); // Die ersten n Primzahlen bestimmen und in pz speichern
printf("Die Summe lautet: %llu", addition(n, pz));
return 0;
}
Weiter geht es dann mit der Funktion zur Addition der ersten n Primzahlen. Die if-Bedingung ist hier eingebaut um eben genau mein Problem zu lösen, ist zwar nicht elegant... aber schnell implementiert
.Das Vorgehen sieht dann so aus: Ich starte das Programm mit Übergabeparameter n = 150000 ... und bekomme als Summe 1709600813, was leider nicht stimmt. Ich bin mir allerdings sehr sicher, dass der Algorithmus stimmen sollte denn für die Summe aller Primzahlen unter 100000 liefert er das richtige Ergebnis.
Meine Vermutung (gestützt durch stundenlanges googlen) geht dahin, dass irgendwo ein overflow passiert, aber soweit ich das sehe sollte unsigned long long int für das erwartete Ergebnis 142913828922 locker ausreichen.
Daher meine Frage: Was übersehe ich? Wo kommt er weshalb nicht hin mit dem Datentyp?
gruß