windows - Big Prime Numbers i c

Indlæg af Hanne Mølgaard Plasc

Problem



Jeg laver et andet spørgsmål fra Eular Problem-siden.
Summen af ​​primerne under 10 er 2 + 3 + 5 + 7=17.
Find summen af ​​alle primaterne under to millioner.


Jeg har formået at skrive koden nedenfor, men jeg tror et sted langs linjen (nemlig når vi kommer til store prime numre) koden taber nøjagtighed. Svaret skal være 142913828922, men jeg får 1179908154.


Jeg ved ikke hvorfor jeg ikke får svaret, fordi koden nedenfor virker til under 10.


Enhver hjælp ville være fantastisk. grunden til at gøre disse problemer er at blive bedre ved C.


kode:


#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
", i);
            prime += i;
        }
    }

    printf("The sum of primes under \%lu: \%lu
",number, prime);
    printf("count: \%d
", 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: 
");
    scanf("\%ul", &number );
    CalcNumber(number);
    return EXIT\_SUCCESS;
}

Bedste reference


I betragtning af længden af ​​nummeret skal du bruge en datatype længst mindst 64 bit. Den nyere C99-standard indeholder long long (og unsigned long long) datatype, der er mindst 64 bit. Hvis du har brug for printf dem, skal du bruge "\%lld" og "\%llu".

Andre referencer 1


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

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


Bemærk at du tjekker omtrent dobbelt så mange numre som du har brug for. Det eneste lige primtal er 2, så der er ingen point, der kontrollerer noget andet end ulige tal større end eller lig med 3 - og tilføj 1+2 'for hånd'. Du kan lige så godt bruge i += 2; her.


Din isPrime() metode vil genberegne en masse oplysninger. Hvad PE er virkelig ved at bruge Sieve of Eratosthenes til at bygge en tabel med primtal og derefter summere primerne fra at . [17]


Men hvis du virkelig vil fortsætte med din nuværende isPrime() metode, vil jeg gerne give en meget stærk antydning om, at du slipper test variablen helt og return fra metoden straks , når du kender et nummer, er det ikke en ide. Det vil føre til, at kode, der er lettere at læse og lettere at fejle.


Overvej at skrive nogle test sager, der tester isPrime() specifikt. Tjek de sædvanlige mistænkte: 1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17 osv.

Andre referencer 2


Din variabel, der lagrer summen af ​​primtalet, er usigneret lang, og det usignerede lange interval er fra 0 til 4294967295. Det kan ikke holde 142913828922 nummer.
142913828922 mod (4294967295 + 1)=1179908154


Skift din datatype