1

unsigned longlongintでの作業と関係があると推測できます。

#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long int uint64;

int main(int argc, char *argv[])
{



    uint64 number_in_question = 600851475143LL;

    long double sqrt_in_question = sqrt(number_in_question);
    bool primes_array[number_in_question+1];



    for (uint64 i = 0; i <= number_in_question; i++) {
        primes_array[i] = true;
    }

    for (uint64 i = 2; i <= sqrt_in_question; i++) {
        if(primes_array[i] == true) {
            // for every multiple of this prime, mark it as not prime
            for (uint64 ii = i*2; ii <= number_in_question; ii += i) {
                primes_array[ii] = false;           
            }
        }
    }   

    for (uint64 i = 0; i <= number_in_question; i++) {
        if(primes_array[i] == true)
        cout << i << ", ";
    }


    system("PAUSE");


    return EXIT_SUCCESS;
}

編集1：私がやろうとしていることの背景：

私はこのテクニックを模倣しようとしています：http：//en.wikipedia.org/wiki/Sieve_of_Eratosthenes 配列を使用して、単純な「プライムですか」を保存している間、1は「はい」、0は「いいえ」です。最終目標はこれを解決することです：

What is the largest prime factor of the number 600851475143 ?ここにリストされています：http：//projecteuler.net/problem=3。私は素数に取り組んでいて、それから素因数に取り組みます。

Edit2：

私が投稿したウィキペディアのリンクを見て、彼らがpuesdocodeを持っていることに気付き（それをスキップして私が持っているものを思いついた）、このメモがあったことに気づきました：広い範囲は完全にメモリに収まらないかもしれません。これらの場合、範囲の一部のみが一度にふるいにかけられるセグメント化されたふるいを使用する必要があります。[14] ふるい分け素数をメモリに保持できないほど広い範囲では、代わりにSorensonのようなスペース効率の良いふるいが使用されます。したがって、「セグメント化されたふるい」方式を使用してこれを行う方法を考える必要があります。

Edit3：

[0]要素を考慮して配列を変更したため、「問題」は、将来の参照には大きすぎる配列メモリサイズにのみ焦点が当てられます。また、配列をuint64ではなくboolとして格納しました。

4

3 に答える 3

5

uint64length の配列を割り当てようとしてい600851475143ます。8 バイトの場合uint64、この配列がメモリ600851475143*8byteを占有することを意味します。4.5TBシステムが大量のメモリを割り当てることができる場合でも (可能性は低いですが)、通常は数 MB に限定されたサイズのスタックに配置しようとしています。さらに、 index に書き込もうとしていますがnumber_in_question、配列の最後のインデックスは ですnumber_in_question-1。

于 2012-01-12T16:08:27.870 に答える
3

配列を作成しようとすると、スタックが吹き飛ばされていると思います。その配列のサイズは非常に大きく、成功する可能性さえあるためにヒープ上に作成する必要があります。

于 2012-01-12T16:01:02.920 に答える
0

配列には、0 から number_in_question - 1 までの番号が付けられた「number_in_question」要素があります。

uint64 の配列を割り当てて、各要素に 0 または 1 を格納するのはなぜですか?

編集：また、そのような可変サイズの配列をスタックに割り当てることはできません。そのスペースをヒープに割り当てるには、 new を使用する必要があります。繰り返しますが、システムでそれだけのスペースを割り当てることができると仮定します。

于 2012-01-12T16:06:27.020 に答える