Большие простые числа в c - PullRequest
Новая
       39

Большие простые числа в c

1 голос
/ 14 марта 2012

Я делаю еще один вопрос со страницы проблем Eular. Сумма простых чисел ниже 10 составляет 2 + 3 + 5 + 7 = 17. Найдите сумму всех простых чисел ниже двух миллионов.

Мне удалось написать код ниже, но я думаю, что где-то вдоль линии (а именно, когда мы добираемся до больших простых чисел), код теряет точность. Ответ должен быть 142913828922, но я получаю 1179908154.

Я не знаю, почему я не получаю ответ, потому что приведенный ниже код работает меньше 10.

Любая помощь будет великолепна. причина, по которой я решаю эти проблемы, состоит в том, чтобы поправиться в C.

код: 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* Initialise */
void CalcNumber(unsigned long number);
int isPrime(unsigned long number);

/* Functions*/

void CalcNumber(unsigned long number)
{
    unsigned long i = 1;
    unsigned long prime = 0;

    while(i != number)
    {
        i++;
        if(isPrime(i))
        {
            printf("prime: %lu\n", i);
            prime += i;
        }
    }

    printf("The sum of primes under %lu: %lu\n",number, prime);
    printf("count: %d\n", i);

}

int isPrime(unsigned long number)
{
      int i, nb, count, test,limit;
      test = count = 0;
      nb = number;
      limit = sqrt(nb) + 1;

      if(nb == 2)
      {
          return 1;
      }

      if (nb % 2 == 0)
              test = 1;
      else{
          for (i = 3 ; i < limit && ! test; i+=2, count++)
            if (nb % i == 0)
              test = 1;
      }
      if (!test)
              return 1;
      else
              return 0;
}

int main(void)
{
    unsigned long number;

    printf("Enter a number: \n");
    scanf("%ul", &number );
    CalcNumber(number);
    return EXIT_SUCCESS;
}

Ответы [ 3 ]

4 голосов
/ 14 марта 2012

Учитывая длину числа, вы должны использовать тип данных длиной не менее 64 бит. Более новый стандарт C99 включает тип данных long long (и unsigned long long), который составляет не менее 64 бит. Если вам нужно printf их, вы должны использовать "%lld" и "%llu".

2 голосов
/ 14 марта 2012

Ваша переменная, в которой хранится сумма простых чисел, имеет длину без знака, а длинный диапазон без знака составляет от 0 до 4294967295. Она не может содержать число 142913828922. Мод 142913828922 (4294967295 + 1) = 1179908154

Изменить тип данных

2 голосов
/ 14 марта 2012 
void CalcNumber(unsigned long number)
{
    unsigned long i = 1;
    unsigned long prime = 0;

    while(i != number)
    {
        i++;
        if(isPrime(i))
        {
            printf("prime: %lu\n", i);
            prime += i;
        }
    }

Обратите внимание, что вы проверяете примерно вдвое больше чисел, чем нужно.Единственное четное простое число - 2, поэтому нет смысла проверять что-либо, кроме нечетных чисел, больших или равных 3, и добавлять 1+2 «вручную».Вы можете также использовать i += 2; здесь.

Ваш метод isPrime() пересчитает много информации.То, что на самом деле * получает, использует Сито Эратосфена , чтобы построить таблицу простых чисел, а затем сложить простые числа из , .

* 1016.* Но если вы действительно хотите продолжить с вашим текущим isPrime() методом, я бы хотел дать очень сильный намек на то, что вы полностью отбросите переменную test и return из метода немедленно когда вы знаете, что число не простое.Это приведет к тому, что код, который будет легче читать и , будет легче отлаживать.

Подумайте о написании некоторых тестовых примеров, специально проверяющих isPrime().Проверьте обычных подозреваемых: 1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17 и т. Д.

...