Frage zu Overflowproblem bei bildung von Summe aus Primzahle

Schnelle objektorientierte, kompilierende Programmiersprache.
Antworten
camus
Beiträge: 1
Registriert: Mo Dez 21, 2015 12:00 am

Frage zu Overflowproblem bei bildung von Summe aus Primzahle

Beitrag von camus » 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.

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 :D .
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ß

Benutzeravatar
naums
Beiträge: 740
Registriert: Sa Jan 02, 2010 10:40 pm
Kontaktdaten:

Re: Frage zu Overflowproblem bei bildung von Summe aus Primz

Beitrag von naums » Mo Dez 21, 2015 10:54 am

Hallo.

Ein paar generelle Anmerkungen:

* benutze Aussagekräftige Variablennamen, es ist total schwer Code von anderen Leuten zu lesen, und wenn dann die Variablen a,b,c heißen hilft das nicht sonderlich.
* Warum speicherst du dir alle Primzahlen? Warum gehst du nicht in einer Schleife alle Zahlen durch, und addierst alle Primzahlen direkt auf, ohne sie in einem Feld abzuspeichern.

Und was genau tut auf Zeile 46 diese If-Bedingung:

Code: Alles auswählen

if( pz[i] < 200000 )
Das schaut für mich ziemlich danach aus, dass du alle Primzahlen unter 200.000 aufaddierst. Das ist nicht die Aufgabe und solcher Programmierstil wiederstrebt auch dem Gedanken von Funktionen etwas, weil diese Funktion genau für einen Anwendungsfall gemacht ist.

Du könntest bspw. einen Maximumswert der Funktion übergeben, und wenn die Schleife eine Primzahl erreicht, die größer als dieser Maximalwert ist, mit return aus der Funktion zurückkehrt.

Löst das bereits dein Problem?

MfG
.globl truth
truth:
mov r0, #42
mov pc, lr

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Frage zu Overflowproblem bei bildung von Summe aus Primz

Beitrag von cloidnerux » Mo Dez 21, 2015 11:50 am

Probier es mal statt

Code: Alles auswählen

 int long long unsigned
mit
unsigned long long int
als Datentyp für deinen Parameter sum und als Rückgabewert deiner Funktion.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Antworten