Summe berechnen?
Man soll von 2 bis 4294967296 alle Primzahlen addieren. Hat dafür jemand nen passendes Programm und dafür das Ergebnis?
Danke!
1 Antwort
C++:
#include <iostream>
bool isPrime( __int64 );
void main()
{
__int64 zahl,summe;
/*
isPrime() erkennt Primzahlen ab 5,
deshalb bei 5 beginnen, und die Summe schon mal auf 2+3
setzen. Es werden nur ungerade Zahlen getestet.
*/
for (summe=2+3, zahl=5; zahl <= 4294967296 ; zahl+=2)
{
if ( isPrime(zahl))
summe += zahl;
}
printf("Die Summe aller Primzahlen beträgt %I64d\n", summe);
}
bool isPrime
(
__int64 zahl
)
{
if (zahl <= 1)
return false;
if (zahl % 2 == 0 || zahl % 3 == 0)
return false;
for (__int64 i = 5; i * i <= zahl; i += 6)
if (zahl % i == 0 || zahl % (i + 2) == 0)
return false;
return true;
}
Welches Programm sollte ich am besten dafür benutzen?
Wenn man die berechneten Primzahlen speichert und in isPrime() benutzt, geht es deutlich schneller:
> g++ -O2 -DNDEBUG listprimes.c++ && time ./a.out
Sum of primes up to 4294967296
Estimated count is 4294967296/17=252645135.
Die Summe aller 203280221 Primzahlen bis 4294967296 beträgt 425649736193687430
real 103m10,940s
user 103m8,121s
sys 0m0,592s
Ich empfehle GNU's g++. Der kostet nix und produziert flotte Executables.
Doch: g++ ist der C++-Compiler der Free Software Foundation.
Geht der? Kannst du mir sonst nen link schicken? https://www.programiz.com/cpp-programming/online-compiler/
Ja, der sollte gehen (falls er keine Laufzeitbegrenzung hat). Kopiere einfach den korrigierten Quelltext rein, klicke auf „Run“ und lehn Dich zurück.
Hier hast Du eine lauffähige Version mit Zwischenausgaben und de Möglichkeit, in Zeile 9 eine kleinere Obergrenze zu setzen (zum Testen):
#include <iostream>
typedef uint64_t __int64;
bool isPrime( __int64 );
int main()
{
__int64 zahl,summe;
const __int64 limit = 4294967296lu/100;
/*
isPrime() erkennt Primzahlen ab 5,
deshalb bei 5 beginnen, und die Summe schon mal auf 2+3
setzen. Es werden nur ungerade Zahlen getestet.
*/
for (summe=2+3, zahl=5; zahl <= limit ; zahl+=2)
{
if ( isPrime(zahl))
summe += zahl;
if ( zahl % 10000000 == 1 || zahl==limit )
{
printf( "%10lu \r", zahl );
fflush(stdout);
}
}
printf("Die Summe aller Primzahlen bis %lu beträgt %lu\n", limit, summe);
return true;
}
bool isPrime
(
__int64 zahl
)
{
if (zahl <= 1)
return false;
if (zahl % 2 == 0 || zahl % 3 == 0)
return false;
for (__int64 i = 5; i * i <= zahl; i += 6)
if (zahl % i == 0 || zahl % (i + 2) == 0)
return false;
return true;
}
Wie findest du meinen Code? #include <iostream>
#include <vector>
#include <cmath>
bool istPrim(unsigned long long n) {
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (unsigned long long i = 3; i <= sqrt(n); i += 2) {
if (n % i == 0) return false;
}
return true;
}
int main() {
unsigned long long summe = 0;
for (unsigned long long i = 2; i <= 4294967296; ++i) {
if (istPrim(i)) {
summe += i;
}
}
std::cout << "Die Summe aller Primzahlen von 2 bis 4294967296 ist: " << summe << std::endl;
return 0;
}
#include <vector>
Wozu das?
for (unsigned long long i = 3; i <= sqrt(n); i += 2) {
i<=sqrt(n) hat Rundungsprobleme: sqrt(p²) könnte einen Wert liefern, der ganz knapp unter p liegt, und ein großer int64 kann nicht exakt in einen double umgewandelt werden. Deine Schleife wird also manche Quadratzahlen als prim erkennen, weil sie zu früh endet.
Rammstein prüft stattdessen i*i<=n. Das ist sicher und vermutlich auch schneller.
Außerdem testest Du jeden Teiler 2k+1. Das sind 50% mehr Tests als mit Rammsteins 6k±1.
Danke! Welchen Code sollte ich jetzt verwenden?
Erste Antwort: Deinen eigenen natürlich!
Aber ich habe dich gewarnt: Er könnte falsche Ergebnisse liefern. Probiere also beide aus (oder verbessere Deinen eigenen Code).
Dann nehme ich den korrigierten von Rammstein. Was ist mit deinem?
Meiner? Ich habe nur Rammsteins Code umgeschrieben und teste nur Primteiler. Das ist nur 1/16 aller Zahlen (bei Rammstein 1/3, bei dir 1/2).
Dazu muss ich aber alle berechneten Primzahlen speichern, was im vollen Lauf 2 GB speicher frisst. Ich weiss nicht, ob der Onlinecompiler das erlaubt, aber Du kannst ja mal testen:
#include <iostream>
#include <cmath>
typedef uint64_t number;
bool isPrime( number zahl ) // zahl >= 5
{
if ( zahl % 3 == 0 )
return false;
for ( number i = 5; i*i <= zahl; i += 6 )
if ( zahl % i == 0 || zahl % (i + 2) == 0 )
return false;
return true;
}
const number step = 1000000
, limit = 4294967293lu/10;
number *primes;
bool isPrime2 ( number zahl ) // zahl >= 5
{
for ( number i = 0; primes[i] && primes[i]*primes[i] <= zahl; ++i )
if ( zahl % primes[i] == 0 )
{
//printf( " %lu teilt %lu\n", primes[i], zahl );
return false;
}
return true;
}
int log ( number n )
{
int l=1;
while ( n >>= 2 )
++l;
return l;
}
int main()
{
printf( "Sum of primes up to %lu\n", limit );
printf( "Estimated count is %'lu/%d=%'ld.\n", limit, log(limit), limit/log(limit) );
primes = (number*)calloc(limit/log(limit), sizeof *primes); // ~N/log N
primes[0] = 2, primes[1] = 3;
number zahl, summe=2+3, count=2;
// bei 5 beginnen und nur ungerade Zahlen testen
for (zahl = 5; zahl <= limit; zahl += 2)
{
if ( isPrime2(zahl) )
{
summe += zahl;
primes[count] = zahl;
++count;
//printf( " primes[%10lu]=%10lu\n", count, zahl );
}
if ( zahl % step == 1 || zahl==limit )
{
printf( "\r%10lu %10lu ", zahl-1, count );
fflush(stdout);
}
}
printf("\nDie Summe aller %lu Primzahlen bis %lu beträgt %lu\n", count, limit, summe);
return 0;
}
Ich habe den Code von Rammstein eingegeben, akzeptiert er nicht 🤷♂️
Ich nutze Visual Studio 2022 von Microsoft. Die Community-Version ist voll funktionsfähig und kostenlos.
Der Code in der Antwort funktioniert nur mit dem Compiler von Microsoft. Ich habe Dir weiter oben schon eine Korrektur gepostet, die dem C++-Standard entspricht (und zusätzlich noch Zwischenausgaben ausspuckt).
Nur die letzte Version von mir ist anders: Sie verwaltet ein Array von Primzahlen und ist dadurch deutlich schneller, braucht aber auch viel mehr Speicherplatz.
Super, danke dir! Ich probiere mal meinen (korrigiert) und Rammsteins (von dir korrigiert) aus. Muss ich bei deinen noch auf 4294967296 setzen und wann merke ich, wann er fertig ist?
Mit einer "normalen" CPU ist der Rechner sicher mehrere Stunden beschäftigt. Abschätzungen aufgrund kleinerer Endwerte sind ungenau, weil die Laufzeit von isPrime() immer weiter ansteigt. Da kann man aber noch viel optimieren.
Mein Code war nur als Vorschlag gedacht. Man könnte z.B. ein Bit-Array mit 4294967296 Elementen aufbauen und dann das Sieb von Eratosthenes anwenden. Das läuft sicher schneller.
Ich benutze jetzt mein Code. Mal sehen, wie lange es dauert 😅
Das von dir kommt bloß auf 54057787600298. Ich weiß echt nicht, wie ich auf die echte Zahl kommen soll 🤷♂️
Du: 4762888964838152
Ich: 425649736193687430
Wahrscheinlich hast Du noch das „/10“ zum Testen drin.
Achtung: Bei zehnfachem Wert läuft das Programm vermutlich hundertmal so lang! Nur meine Version verhält sich etwas besser, weil die Dichte der Primzahlen langfristig gegen 0 geht.
Ist dein Wert der genaue oder wurde dort auch abgebrochen?
In meiner Version steht sowas wie „limit=4294967293lu / 10;“, um den Zahlenbereich und damit die Rechenzeit zu begrenzen. Das ist nur zum Testen gedacht. Bei „/10“ ist die Summe nur 4762888964838152, und bei „/100“ nur 54057787600298.
Die Summe über alle Primzahlen bis 2³² ist exakt 425649736193687430. Das dauert halt etwas (auf meinem Rechner knapp 2 Stunden, der Online-Rechner ist vielleicht schneller).
Achtung: Bei mir stoppt der Onlinerechner, wenn ich in ein anderes Fenster wechsle. Du wirst also während der Berechnung nichts anderes am Computer machen können.
Das ist der exakte Wert? Ich habe jetzt die exakte Summe?
Klar doch. Das habe ich doch schon gestern um 22:05 Uhr gepostet.
Ich habe es gerade in die Aufgabe eingetippt. Es stimmt einfach
Kannst du den Code schicken, welchen du benutzt hast?
Du hast die 2 vergessen und die 3 nicht erkannt:
Und __int64 ist kein Standard-Typ. So geht's aber:
Und für die ersten 10% bekomme ich:
Das volle Programm sollte also ca. in 24 Stunden durch sein.