Почему я проваливаю проект Euler # 10?
-
22-09-2019 - |
Вопрос
Вопрос в том,:Найдите сумму всех простых чисел меньше 2 миллионов.
Я в значительной степени использовал Сито Erastothenes, и приведенная ниже программа, похоже, работает для небольшого числа, т.е.определите ЛИМИТ как 10L, и в качестве ответа получите 17.
Я отправил 1179908154 в качестве ответа, созданного следующей программой, и это было неверно.
Пожалуйста, помогите указать на проблему.Спасибо.
#include <stdio.h>
#define LIMIT 2000000L
int i[LIMIT];
int main()
{
unsigned long int n = 0, k, sum = 0L;
for(n = 0; n < LIMIT; n++)
i[n] = 1;
i[0] = 0;
i[1] = 0;
unsigned long int p = 2L;
while (p*p < LIMIT)
{
k = 2L;
while (p*k < LIMIT)
{
i[p*k] = 0;
k++;
}
p++;
}
for(n = 0; n < LIMIT; n++)
if (i[n] == 1)
{
sum += n;
}
printf("%lu\n",sum);
return 0;
}
Решение
Вы правильно вычисляете простые числа, но сумма слишком велика (более 2^32) и не помещается в беззнаковый 32-битный формат.Вы можете использовать 64-битное число (long long
в некоторых компиляторах), чтобы это исправить.
Другие советы
Ваша логика вроде бы правильная, но вы путаете типы данных и их диапазоны. Проверьте, работает это или нет:
#include <stdio.h>
#define LIMIT 2000000
int i[LIMIT];
int main()
{
long long int n = 0, k, sum = 0;
for(n = 0; n < LIMIT; n++)
i[n] = 1;
i[0] = 0;
i[1] = 0;
long long int p = 2;
while (p*p < LIMIT)
{
k = 2;
while (p*k <LIMIT)
{
i[p*k] = 0;
k++;
}
p++;
}
for(n = 0; n < LIMIT; n++)
if (i[n] == 1)
{
sum += n;
}
printf("%lld\n",sum);
return 0;
}
Output :142913828922
Вы также можете обнаружить, что вам нужно использовать переключатель компилятора -std=c99 также хорошо.Я сделал это с gcc (GCC) 3.4.5 (mingw-vista special r3).
т. е.
gcc -Wall -std=c99 -o проблема 10 проблема 10.c