Code:
// primefactors.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
//
#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <stack>
#include <list>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
// Erster Programmteil, erstellen der primelist
int stop = 0, z = 0;
const unsigned int border = 1000000;
std::vector<int> list;
//auto count = std::begin(list);
for (int b = 0; b < border; b++) list.push_back(b);/*Liste von 0-border-1 anlegen*/
int primenumber = 2;
int counter = 2; unsigned int number = 2;
while (primenumber <= border / 2 && stop == 0)/*vielfache der Primzahl nullen*/
{
while (primenumber <= border / 2 && counter*primenumber < border - 1)
{
list[primenumber * counter] = 0;
counter += 1;
}
if (++number < border) { primenumber = list[++number]; } /*nächste Primzahl finden*/
else { stop = 1; }
counter = 2;
while (primenumber == 0 && primenumber < border)
{
primenumber = list[++number];
}
}
std::vector<int> primelist;
for (auto it = std::begin(list); it != std::end(list); ++it)
if (*it != 0) primelist.push_back(*it);
while (!list.size()) list.pop_back();
list.resize(0);
//for (int i = 0; i < 10; i++) std::cout << primelist[i] << ';' ; /* Kontrolle *(
std::cout << ',' << 'r' << 'e' << 'a' << 'd' << 'y' << ',' ;
// Zweiter Teil, berechnen der Primeteiler
unsigned long long int summe = 0, upperborder = pow(10, 8);
int m = 0, psize = 0;
/*for (int zahl = 1; zahl <= upperborder; m = pow(zahl, 15) + 1, zahl += 1)
{
psize = primelist.size();
for (int rest = zahl, i = 0, counter = primelist[i]; rest > 0 && i < psize; i++)
{
if (rest % counter == 0) { for (; rest / counter == 0; rest /= counter); summe += counter; }
counter += 1;
}
}*/
// Zweiter Teil, neue herangehensweise:
std::vector<int> result;
for (int b = 0; b < upperborder; b++) result.push_back(b);/*Liste von 0-border-1 anlegen*/
std::cout << 'f' << 'i' << 'n' << 'a' << 'l' << 'y' << ',' << summe ;
for (int i = 0; i < 10; i++) std::cout << pow(i, 15) + 1 << ';';
std::cin >> stop;
return 0;
Code:
// primefactors.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
//
#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <stack>
#include <list>
#include <limits.h>
#include <chrono>
using namespace std;
using namespace std::chrono;
int _tmain(int argc, _TCHAR* argv[])
{
// Erster Programmteil, erstellen der primelist
int stop = 0, z = 0;
unsigned int border = pow(10,6) /*muss spaeter pow(10,8) sein*/, newborder = pow(10,4); /*muss spaeter pow(10,11) sein*/
std::vector<int> vektor;
vektor.resize(border);
high_resolution_clock h;
float tone = static_cast<unsigned>((h.now() - system_clock::from_time_t(system_clock::to_time_t(h.now()))).count() * static_cast<float>(1000) / high_resolution_clock::period::den);
for (int b = 0; b < border; b++) vektor[b] = b;/*Liste von 0-border-1 anlegen*/
int primenumber = 2;
int counter = 2; unsigned long long int number = 2;
while (primenumber <= border / 2 && stop == 0)/*vielfache der Primzahl nullen*/
{
while (primenumber <= border / 2 && counter*primenumber < border - 1)
{
vektor[primenumber * counter] = 0;
counter += 1;
}
if (++number < border) { primenumber = vektor[++number]; } /*nächste Primzahl finden*/
else { stop = 1; }
counter = 2;
while (primenumber == 0 && primenumber < border)
{
primenumber = vektor[++number];
}
}
int ttwo = static_cast<unsigned>((h.now() - system_clock::from_time_t(system_clock::to_time_t(h.now()))).count() * static_cast<float>(1000) / high_resolution_clock::period::den);
vector<int> primelist;
for (auto it = std::begin(vektor); it != std::end(vektor); ++it)
if (*it > 1) primelist.push_back(*it);
vektor.clear();
std::cout << 'r' << 'e' << 'a' << 'd' << 'y' << ',';
int zahl = 1, ueberlauf = 0;
unsigned long long int summe = 0;
while (zahl < newborder)
{
number = pow(zahl, 15) + 1;
counter = 0;
while (number > 1 && counter < primelist.size())
{
if (number % primelist[counter] == 0)
{
if (summe + primelist[counter] > 18446744073709551615) ueberlauf += 1;
summe += primelist[counter];
for (; number % primelist[counter] == 0;) { number = number / primelist[counter]; }
}
counter++;
}
zahl++;
}
std::cout << 's' << 'u' << 'm' << 'm' << 'e' << '=' << summe << ';';
std::cout << 'f' << 'i' << 'n' << 'a' << 'l' << 'y' /*<< summe << '/'*/;
if (ueberlauf != 0) std::cout << 'u' << 'e' << 'b' << 'e' << 'r' << 'l' << 'a' << 'u' << 'f' << '=' << ueberlauf;
std::cout << '-' << '>' << ttwo - tone; //Zeit zum erstellen der liste?
std::cin >> stop;
return 0;
}Hier ist die genaue Aufgabenstellung: https://projecteuler.net/problem=421
Ich möchte hier ausdrücklich keine Lösung sondern nur Hinweise wie ich mein Programm optimieren kann.
Ich bin selbst noch Programmier anfänger, lese zwar u.a. die c++ einführung von Ulrich Breymann aber habe nur wenig Erfahrung. So habe ich mich z.B. heute das erste mal mit Stacks beschäftigt weil ich mit den normalerweise für arrays vorgesehenen 4 MB nicht mal ansatzweise auskam. Seid also bitte nachsichtig wenn ich murks produziert habe
Wie ich es bereits in anderen Aufgaben im Zusammenhang mit Primzahlen gemacht habe erstelle ich im ersten Teil eine liste aller benötigten primzahlen (hier unter 10^8) in 5 sek, dieser Teil funktioniert dank des Sieb des Eratosthenes schnell genug.
Der 2 Teil braucht jedoch deutlich länger. Meine erste Idee jede Zahl unter 10^11 einzeln zu erstellen, die primfaktoren mithilfe der im ersten Teil erstellten Liste zu finden und sich erst dann mit der nächsten Zahl zu beschäftigen habe ich erstmal verworfen.
Meine Überlegung war, dass ich erstmal eine liste aller zahlen unter 10^11 anlege und diese später in einem durchlauf abarbeite, dh. beim ersten schleifendurchlauf gucke welche zahlen durch 2 Teilbar sind, beim nächsten welche durch 3 Teilbar sind und so weiter... Die Abfrage müsste man später ja auch hervorragend parallelisieren können. Jedoch habe ich ein großes Problem, mein eigener PC hat nicht die beste Hardware und bisher habe noch keine Entwicklungsumgebung auf den Uni servern so verändert, dass ich darauf c++ programme schreiben kann. (Ich habe dort lediglich mit Python/bash gearbeitet) Bisher habe ich mich da auch nicht wirklich mit beschäftigt weil die Code optimierung eine viel größere Wirkung haben müsste.
Zurzeit überlaste ich meinen PC aber bereits damit eine liste aller Zahlen bis 10^9 anzulegen. Aufgrund meines Q6600 Prozessors, nur 6 GB DDR2 Ram und der tatsache das meine SSD nur über sata2 angeschlossen ist braucht mein PC mehr als 10 min bis ich die fertige liste aller zahlen bis 10^9 habe. Davon eine liste bis 10^11 anzulegen möchte ich gar nicht reden. Aufgrund der großen Zahlen die ich am ende habe (bis zu 100 Milliarden) sollte ich diese evtl doch direkt bearbeiten statt sie erst zwischenzuspeichern? Dafür müsste ich dann halt jede zahl einzeln durchrechnen. Das müsste aber nochmal um ein vielfaches länger dauern als das anlegen der liste oder habe ich da irgendeinen besonders schnellen befehl übersehen?
Anmerkung: ich habe gerade eine info über das Quadratisches Sieb gefunden aber selbst das müsste doch ewigkeiten brauchen um eine derartige Anzahl an Zahlen zu zerlegen, oder?
Im Zweifelsfall habe ich auch zugriff auf 4 oder 8 GeForce GTX 470 Grafikkarten und dank vs 2013 pro auch die entsprechenden librarys um solche programme zu erstellen. Jedoch dürfte das, so interresant es auch wirkt noch umfangreicher werden.
Ich würde mich dann jetzt daran machen doch jede Zahl nacheinander durchzurechnen, dies könnte man später ja ebenfalls paralellisieren. Aber so oder so dürfte das nicht mal annähernd schnell genug sein, Tips sind also gerne gesehen.
Zuletzt bearbeitet:
Ich schaue mir das nacher nochmal genauer an.
