for(i=2;i<=n;i++)
{
flag=0;
for(j=2;j<=sqrt(i);j++) //Looping till square root of n times
{
if(i%j==0)
{
flag=1;
break;
}
}
if(flag==0)
sum+=i;
}
Zeit genommen sind zu laufen länger als 5 Sekunden, aber die Frist, die die Frage Anforderungen weniger als 5 Sekunden. Kann jemand eine optimierte Lösung vorschlagen? Danke!Programm Summe von Primzahlen finden zwischen 1 und 10^7
std::vector<uint> primes = {2,3,5};
bool check_prime(uint x){
bool result = true;
for(auto i: primes){
if(i*i>x){
break;
}
if(x%i==0){
result = false;
break;
}
}
if(result){
primes.push_back(x);
}
return result;
}
void get_primes(){
for(uint x =6; i<N; i++){
check_prime(x);
}
}
uint get_sum(){
return std::accumulate(primes.begin(), primes.end(), 0, std::plus);
}
Und was willst du uns sagen? –
Während dieses Code-Snippet die Frage lösen kann, [hilft eine Erklärung] (http://meta.stackexchange.com/questions/114762/explaining-entirely-code-based-results) wirklich, um die Qualität Ihres zu verbessern Post. Denken Sie daran, dass Sie die Frage für Leser in der Zukunft beantworten, und diese Leute könnten die Gründe für Ihren Codevorschlag nicht kennen. – NathanOliver
check% == 0 nur für "bekannte" Primzahlen, nicht alle Zahlen in [2; sqrt (x)] –
Ich schlage vor, Sie werfen Sie einen Blick auf die Sieve of Eratosthenes algorithm
Dieser Algorithmus Code optimieren.
Verwenden Sie ein [Sieb von Eratosthenes] (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) auf dem Bereich und Summe der Primzahlen, die Sie finden. – NathanOliver
2 ist Primzahl. Alle anderen Primzahlen sind ungerade, was die Zahl der zu prüfenden Zahlen halbiert. – rossum
statt mit allen Zahlen zu überprüfen, nur mit zuvor gefundenen Primzahlen überprüfen und natürlich gerade Zahlen überspringen. –