Konsolen-Programme mit C++
"Jede gerade Zahl größer als 2 kann als Summe zweier Primzahlen geschrieben werden."
Das ist doch ein interessantes Thema unter Anwendung einer Konsolenanwendung.|
#include <iostream> #include <limits> #include <cmath> #include <ctime> using namespace std; void wait() { cin.clear(); cin.ignore(std::numeric_limits<streamsize>::max(), '\n'); cin.get(); } namespace MyMath { bool IsPrime(unsigned int number) { for (unsigned int i=2; i<number; i++) { if (number%i == 0) return false; } return true; } } int main() { clock_t zeit1 , zeit2; unsigned int a; zeit1 = clock(); bool gegenbeweis = true; for (unsigned int i=6; i<=500000; i+=2) { if (i%25000 == 0) { zeit2 = clock(); cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl; } for (unsigned int a=2; a<i; a++) { if ((MyMath::IsPrime(a)) && (MyMath::IsPrime(i-a))) { gegenbeweis = false; //cout << a << " " << i-a << " "; break; } } if (gegenbeweis) { cout << "Gegenbeweis gefunden für folgende Zahl: " << i << endl; wait(); } } //wait(); } |
Bei mir auf dem PC sah (zum Zeitpunkt des Tests) die zeitliche Betrachtung wie folgt aus:
25000 time: 621 msExperimentieren und optimieren Sie mit dem Programm. Schauen Sie sich nicht gleich eine mögliche Lösung an.
|
// Beschleunigte Variante (Danke an
das c-plusplus.de Forum, namentlich erwähnen möchte ich Volkard Henkel) #include <iostream> #include <limits> #include <ctime> #include <cstdint> using namespace std; void wait() { cin.clear(); cin.ignore(numeric_limits<streamsize>::max(), '\n'); cin.get(); } bool IsPrime(uint64_t number) { if(number<2) return false; if(number==2) return true; if(number%2==0) return false; for(uint64_t i=3; i*i<=number; i+=2) { if(number%i == 0) return false; } return true; } bool ZweiPrimzahlenGefunden(uint64_t i) { for(uint64_t a=2; a<i; a++) { if(IsPrime(a) && IsPrime(i-a)) return true; } return false; } int main() { clock_t zeit1 , zeit2; zeit1 = clock(); for(uint64_t i=6; i<=5000000; i+=2) { if(!ZweiPrimzahlenGefunden(i)) cout << "Gegenbeweis gefunden für folgende Zahl: " << i << endl; if (i%100000 == 0) { zeit2 = clock(); cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl; } } wait(); } |
Mit -O3 und 64 bit:
5.000.000 time: 18652 ms!
... und nun geben wir
richtig Gas. Danke an Volkard, Bengo, Arcoth u.a. aus dem C++-Forum. Dort finden
auch Sie volle Unterstützung in Fragen von C++.
Ich habe die
BigIntegerLibrary (Alternative: gmp mit gmpxx) eingebunden, um über 2^64 zu
gelangen und x64 als Ziel angegeben:
|
#include <iostream> #include <iomanip> #include <cstdint> #include <cstdlib> #include <algorithm> #include <cmath> #include <ctime> #include <vector> #include "BigIntegerLibrary.hh" using namespace std; void wait() { cout << "Press any key to continue." << endl; cin.clear(); cin.ignore(numeric_limits<streamsize>::max(), '\n'); cin.get(); } //calculates (a * b) % c BigUnsigned mulmod(BigUnsigned a, BigUnsigned b, BigUnsigned mod) { BigUnsigned x = 0; BigUnsigned y = a % mod; while (b > 0) { if (b % 2 == 1) { x = (x + y) % mod; } y = (y * 2) % mod; b /= 2; } return x % mod; } BigUnsigned powmod_Volkard(BigUnsigned base, BigUnsigned exp, BigUnsigned modul) { //rechnet 'base hoch exp mod modul' BigUnsigned a1 = base, z1 = exp, x = 1, m = modul; while (z1 != 0) { while ((z1 % 2) == 0) { z1 /= 2; a1 = mulmod(a1, a1, m); } --z1; x = mulmod(x, a1, m); } return x; } bool IsPrimeMillerRabinOptimized(BigUnsigned n) { /* example: step: "calculate s and d" n = 1001 n-1 = 1000 s = 3 d = 125 1000 / 2^3 = 125 step: "test with base a" ad = a^d mod n (cf. function powmod) */ if (n == 2) return true; // "s" is the logarithm to base base 2 of the biggest number 2^s dividing n-1 // d = (n-1)/(2^s) // calculate d and s BigUnsigned d = n - 1; BigUnsigned s = 0; while ((d & 1) == 0) { ++s; d >>= 1; } // We do not use random base a = {2 ... n-1}, but fix it to a = 2 BigUnsigned a = 2; // base ("witness") BigUnsigned ad = (powmod_Volkard(a%n, d, n)); // (a^d) mod n if (ad == 1) return true; // a^d mod n == 1 if ((s > 0) && (ad == (n - 1))) return true; // a^d mod n == -1 (tests (a^d)^(2^0)) // test for r = {0 ... s-1} for (BigUnsigned r = 1; r < s; ++r) { // ad is currently ad^(2^(r-1)), thus we square it to get ad^(2^r)) ad = mulmod(ad, ad, n); if (ad == (n - 1)) return true; // tests (a^d)^(2^(r+1))) } return 0; // false, composite } bool IsPrimeDivisionTest(BigUnsigned number) { if (number<2) return false; if (number == 2) return true; if (number % 2 == 0) return false; for (BigUnsigned i = 3; i*i <= number; i += 2) { if (number%i == 0) return false; } return true; } bool IsPrime(vector<bool>& primes, BigUnsigned number, BigUnsigned primeLimit) { if (number <= primeLimit) return primes[number.toUnsignedLong()]; // lookup from bitset (in the RAM) return IsPrimeMillerRabinOptimized(number); } bool PrimePairFound(vector<bool>& primes, BigUnsigned i, const BigUnsigned primeLimit) { bool retVal = false; BigUnsigned grenze = i / 2; BigUnsigned a = 0; for (a = 3; a <= grenze; a += 2) { if (IsPrime(primes, a, primeLimit) && IsPrime(primes, i - a, primeLimit)) { retVal = true; break; } } cout << i << " " << setw(5) << a << " "; return retVal; } int main() { BigUnsigned startNumber = stringToBigUnsigned("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"); BigUnsigned endNumber = stringToBigUnsigned("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000"); uint64_t const primeLimit = 100000000; //200000000000; cout << "We generate vector<bool>(primes) up to: " << primeLimit << endl; // (this amount depends on the capability of your RAM) vector<bool> primes(primeLimit); // processed numbers; time_t startTime, endTime; // measuring execution time uint64_t global_count = 0; // total number of primes time(&startTime); // initialize the number array primes[0] = false; primes[1] = false; for (uint64_t i = 2; i<primeLimit + 1; ++i) { primes[i] = true; } // sieving loop uint64_t iMax = (uint64_t)sqrt((double)primeLimit) + 1; for (uint64_t i = 2; i<iMax; ++i) { if (primes[i]) { for (uint64_t j = 2 * i; j<primeLimit + 1; j += i) { primes[j] = false; } } } time(&endTime); // count the number of primes for (uint64_t i = 0; i<primeLimit + 1; ++i) { if (primes[i]) global_count++; } cout << "In " << difftime(endTime, startTime) << " s we found " << global_count << " prime numbers (2 to " << primeLimit << " )." << endl << endl; cout << "Now Goldbach first prime number pair will be detected" << endl; clock_t zeit1, zeit2, zeit2_old; zeit2 = zeit1 = clock(); for (BigUnsigned i = startNumber; i <= endNumber; i += 2) { if (!PrimePairFound(primes, i, BigUnsigned((unsigned long)primeLimit))) { cout << "Counterevidence found for this number: " << i << endl; wait(); } zeit2_old = zeit2; zeit2 = clock(); cout << "time: " << 1000 * (zeit2 - zeit2_old) / CLOCKS_PER_SEC << " ms" << endl; } wait(); } |