7

すべてうまくいっているように見えますが、プログラムは正しい答えを教えてくれません。私のは 142,915,960,832 ですが、142,913,828,922 のはずです。差額は 2,131,910 です (まだ紙の数字を引くことができれば)、この 200 万をどこで手に入れたのかわかりません。誰でも私を助けることができますか？

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

#define BELOW 2000000

int isaprime (int num);

int main (void) {

    int i;
    float sum = 0;

    for (i = 2; i < BELOW; i++) {

            if (isaprime(i) == 1) {
                    sum = sum + i;
                    printf ("\n%d\t%.1f", i, sum);
            }
    }

    getch();
    return 0;
}

int isaprime (int num) {

    int i;

    for (i = 2; i <= sqrt(num); i++) {
            if (num % i == 0) {
                    return 0;
            }
            else {
                    ;
            }
    }

    return 1;
}
4

9 に答える 9

10

floatとして使用することsumが問題です。kからのすべての整数[-k, k]が32 ビット float で正確に表現できる最大の整数は 2^24 1です。その後、いくつかの整数で精度が失われ始めます。あなたの合計はその範囲外であるため、ばかげたマージンにより、精度が失われ、すべての賭けが無効になります。

次のようなより大きなタイプに変更する必要がありlongます（マシンで64ビットであると仮定）。変更を加えると、正しい答えが得られます（コードで行ったように）：

[ec2-user@ip-10-196-190-10 ~]$ cat -n euler.c
     1  #include <stdio.h>
     2  #include <math.h>
     3  
     4  #define BELOW 2000000
     5  
     6  int isaprime (int num);
     7  
     8  int main (void) {
     9  
    10      int i;
    11      long sum = 0;
    12  
    13      for (i = 2; i < BELOW; i++) {
    14  
    15              if (isaprime(i) == 1) {
    16                      sum = sum + i;
    17              }
    18      }
    19      printf("sum: %ld\n", sum);
    20  
    21      return 0;
    22  }
    23  
    24  int isaprime (int num) {
    25  
    26      int i;
    27  
    28      for (i = 2; i <= sqrt(num); i++) {
    29              if (num % i == 0) {
    30                      return 0;
    31              }
    32              else {
    33                      ;
    34              }
    35      }
    36  
    37      return 1;
    38  }
[ec2-user@ip-10-196-190-10 ~]$ gcc euler.c -lm
[ec2-user@ip-10-196-190-10 ~]$ ./a.out
sum: 142913828922

1 : 仮数部の 23 の明示的なビットと 1 つの隠しビット。

于 2013-08-10T00:24:04.853 に答える
6

@LeeDanielCrockerが示唆したように、問題を即座に解決するエラトステネスのふるいの実装を次に示します。

#include <stdio.h>
#include <string.h>

#define ISBITSET(x, i) (( x[i>>3] & (1<<(i&7)) ) != 0)
#define SETBIT(x, i) x[i>>3] |= (1<<(i&7));
#define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF;

long long sumPrimes(int n) {
    char b[n/8+1];
    long long i, p;
    long long s = 0;

    memset(b, 255, sizeof(b));
    for (p=2; p<n; p++) {
        if (ISBITSET(b,p)) {
            //printf("%d\n", p);
            s += p;
            for (i=p*p; i<n; i+=p) {
                CLEARBIT(b, i); }}}
    return s; }

int main(void) {
    printf("%lld\n", sumPrimes(2000000));
    return 0; }

ideoneでは、30 ミリ秒で返されます。以下に示す最適化されたバージョンは、奇数のみを選別し、2 を個別に処理し、ideoneでゼロ時間 (10 ミリ秒未満) で実行されます。

#include <stdio.h>
#include <string.h>

#define ISBITSET(x, i) (( x[i>>3] & (1<<(i&7)) ) != 0)
#define SETBIT(x, i) x[i>>3] |= (1<<(i&7));
#define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF;

long long sumPrimes(int n) {
    int m = (n-1) / 2;
    char b[m/8+1];
    int i = 0;
    int p = 3;
    long long s = 2;
    int j;

    memset(b, 255, sizeof(b));

    while (p*p < n) {
        if (ISBITSET(b,i)) {
            s += p;
            j = (p*p - 3) / 2;
            while (j < m) {
                CLEARBIT(b, j);
                j += p; } }
        i += 1; p += 2; }

    while (i < m) {
        if (ISBITSET(b,i)) {
            s += p; }
        i += 1; p += 2; }

    return s; }

int main(void) {
    printf("%lld\n", sumPrimes(2000000));
    return 0; }

素数を使ったプログラミングに興味がある場合は、私のブログでこのエッセイをお勧めします。上記の両方のアルゴリズムについて説明し、Project Euler で素数の問題を解決するために必要なすべてのアルゴリズムをカバーし、C および他の 4 つの言語のソース コードが含まれています。

于 2013-08-10T12:57:52.327 に答える
3

速くて簡単なこの方法を試してください：

int const MAX = 2000000;

int checkPrime(int n){
    int range = n;
    for (int i = 2; i < range; i++){
        if (n%i == 0){
            return 0;
        }
        range = n / i;
    }
    return 1;
}

int solution(){
    double sum = 0;
    for (int i = 2; i < MAX; i++){
        if (checkPrime(i) == 1){
            sum += i;
        }
    }
    return sum;
}
于 2015-05-17T16:15:42.303 に答える
0 
#include<stdio.h>
#define MAX 2000001
long long a[MAX],c=0;
main()
{
     long long i=0,k,j,p,temp=0;
    long long inc=0;
    for(i=0;i<MAX;i++)
    a[i]=i;
    for(j=2;j*j<MAX;j++)
    {   
        temp=j;
        inc=2*temp;
        k=((MAX-1)/temp)-1;
        while(k)
        {
            printf("%d",inc);
            printf("\n");
            if(a[inc]!=0)
            a[inc]=0;
            inc+=temp;
            --k;
        }
    }
    for(p=0;p<MAX;p++)
    {
        if(a[p]!=0)
        c=c+a[p];

        printf("%lld",a[p]);
        printf("\n");
        }
    printf(" The sum is : %lld",c-1);
}
于 2013-08-18T11:35:38.273 に答える