Суммирование простых чисел в переполнении стека
Привет, ребята, я работаю над программой, чтобы дать сумму всех простых чисел до двух миллионов. Вот что у меня есть … и я знаю, что этот метод работает для нахождения простых чисел, потому что я использовал его раньше … однако, когда я запускаю эту программу, я продолжаю получать бесконечный цикл и никакого вывода …. любая помощь будет очень полезна оценили!
#include <iostream>
using namespace std;
int main (int argc, char * const argv[]) {
bool isPrime=true;
int i = 2;
int sum = 0;
do{
for ( int j = 2; j < i; j++)
{
if ( i % j == 0 )
{
isPrime=false;
break;
}
}
if (isPrime)
{
cout << "Prime: " << i << endl;
sum += i; // add prime number to sum
}
i++;
}while(i < 2000000);
cout << "the sum of all the primes below two million is: " << sum << endl;
getchar();
return 0;
}
Решение
Единственная логическая ошибка, которую я могу найти, это то, что вы никогда не переустанавливаете isPrime в true внутри цикла, но это не должно вызывать бесконечный цикл, просто неверные результаты.
Я сомневаюсь, что это идет в бесконечном цикле, хотя, я просто думаю, что это занимает много времени, потому что это неоптимально. Вам не нужно проверять каждый номер до i, sqrt(i) или даже i/2 сделал бы это.
Более того, вы можете создать сито простых чисел (google this), а затем просто сложить их — это будет значительно эффективнее.
Другие решения
Я не думаю, что у вас есть бесконечный цикл. Вы забыли установить isPrime в trueКак заметил Лучиан Григоре, но ваш код также будет работать очень долго. Обратите внимание, что вы можете прекратить пробное деление один раз j*j > i,
Если вы также заинтересованы в том, чтобы сделать вещи более эффективными с минимальными усилиями — чтобы получить простые числа, вам нужно только проверить числа в форме (6n + 1) и (6n + 5)
Итак, включив что-то вроде в ваш основной цикл
int p6 = p % 6;
if (p6 == 1) {
result = isPrime(p);
p += 4;
} else if (p6 == 5) {
result = isPrime(p):
p += 2;
}
Ускорит вас в несколько раз. Не забывайте угловые случаи 2 и 3 все же.