Prime Generator Meluap? C++

Saya sedang menulis generator untuk bilangan prima menggunakan saringan eratosthenes. Saya telah membuatnya berfungsi untuk menghasilkan bilangan prima di bawah 521102 tetapi angka yang lebih tinggi menyebabkan program mogok. Ini kode saya.

#include <iostream>
using namespace std;

int main ()
{
    int long MAX_NUM = 1000000;
    int long MAX_NUM_ARRAY = MAX_NUM+1;
    int Num_Array [MAX_NUM_ARRAY];
    std::fill_n(Num_Array, MAX_NUM_ARRAY, 3);
    int long sieve_prime = 2;
    int long sieve_prime_constant = 0;
    Num_Array [0] = 1;
    Num_Array [1] = 1;



    while (sieve_prime_constant <= MAX_NUM_ARRAY)
    {
        if (Num_Array [sieve_prime_constant] == 1)  
        {

            sieve_prime_constant++;
        }

        else
        {
        Num_Array [sieve_prime_constant] = 0;  
        sieve_prime=sieve_prime_constant; 
            while (sieve_prime<=MAX_NUM_ARRAY - sieve_prime_constant)  
            {
                sieve_prime = sieve_prime + sieve_prime_constant;
                Num_Array [sieve_prime] = 1;
            }

            if (sieve_prime_constant <= MAX_NUM_ARRAY)
            {
                sieve_prime_constant++;
                sieve_prime = sieve_prime_constant;
            }
        }
    } 
return 0;
}

Saya memasukkan MAX_NUM sebagai 1000000 dan tidak berhasil. Tapi seperti yang saya katakan sebelumnya, angka di bawah 521102 bisa digunakan. Saya harus bisa menguji angka yang lebih tinggi. Apa masalah saya, dan bagaimana cara memperbaikinya?

Terima kasih banyak!

Terima kasih atas tanggapannya. Saya mencoba solusi mengalokasikan array secara dinamis. Itu bekerja dengan baik, sampai batas tertentu. Setelah mengatur MAX_NUM menjadi sekitar 500 juta saya mendapatkan kesalahan ini ketika saya menjalankan program...

penghentian dipanggil setelah melempar instance 'std::bad_alloc' what(): std::bad_alloc

Aplikasi ini telah meminta Runtime untuk menghentikannya dengan cara yang tidak biasa. Silakan hubungi tim dukungan aplikasi untuk informasi lebih lanjut.

Memiliki atap 500 juta hampir bisa diterima, tapi lebih tinggi masih lebih baik? Ada ide lain?


c++ arrays overloading generator
person Nathan J    schedule 10.02.2013    source sumber
comment
Jalur manakah sebenarnya yang menyebabkan crash?   -  person Peter L.    schedule 10.02.2013
comment
Anda mungkin menggunakan Windows dan mungkin melebihi batas maksimum tumpukan. Alokasikan array secara dinamis atau alokasikan secara statis (mungkin di luar fungsi) atau temukan cara untuk meningkatkan ukuran tumpukan.   -  person Jonathan Leffler    schedule 10.02.2013
comment
Ini bukan masalahnya, tapi idiom untuk menggunakan int panjang adalah dengan mendeklarasikannya sebagai long.   -  person Pete Becker    schedule 10.02.2013

Jawaban (3)


arrow_upward
3
arrow_downward

Dengan asumsi Anda menggunakan Windows, tumpukan Anda terlalu kecil (1 MB secara default) untuk memuat variabel berikut dalam bingkai tumpukan:

int Num_Array [MAX_NUM_ARRAY];

Anda harus mengalokasikannya di heap:

int *Num_Array = new int[MAX_NUM_ARRAY];
...
delete[] Num_Array;
person JosephH    schedule 10.02.2013
comment
Anda harus mengalokasikannya di heap. - Mengapa? Bukankah memori (yang tidak) diinisialisasi (DATA atau BSS) cukup baik? - person ; 10.02.2013
comment
@ H2CO3 Perbaiki saya jika saya salah, tapi saya pikir itu hanya akan menambah ukuran file yang dapat dieksekusi secara tidak perlu? - person JosephH; 10.02.2013
comment
Jika Anda memiliki keinginan untuk melakukan sedikit perang optimasi prematur: mengapa tidak? Ya, ini mungkin meningkatkan ukuran executable, tapi juga akan lebih cepat karena memiliki alamat yang konstan. - person ; 10.02.2013
comment
@ H2CO3 Oh, kalau begitu saya kira kita berdua bisa sepakat bahwa kita bisa mengalokasikannya di heap selama inisialisasi. - person JosephH; 10.02.2013
comment
@JoesphH Sekadar memperjelas: tidak disarankan untuk mengalokasikan data statis yang masih aktif sepanjang masa program. - person ; 10.02.2013
comment
@H2CO3 Ini semakin konyol. Apa bedanya dengan kode yang disediakan oleh OP? - person JosephH; 10.02.2013

arrow_upward
1
arrow_downward

Mungkin karena Anda menghancurkan tumpukannya. Bagaimana kalau memindahkan array keluar dari fungsi main()?

#define MAX_NUM = 1000000;
#define MAX_NUM_ARRAY (MAX_NUM + 1)
int Num_Array[MAX_NUM_ARRAY];

int main()
{
    // etc.
    return 0;
}
person Community    schedule 10.02.2013

arrow_upward
0
arrow_downward

Fakta bahwa Anda menggunakan std::fill_n menunjukkan Anda sebenarnya menulis C++, bukan C.

Anda dapat secara drastis mengurangi konsumsi memori program Anda dengan menggunakan array bool yang sebenarnya, bukan array int. Karena Anda menggunakan C++, Anda bisa mendapatkan array Boolean menggunakan std::vector<bool>. Tidak seperti bool[n], std::vector<bool>(n) hanya membutuhkan n bit (bool[n] mungkin membutuhkan 8n bit, atau berapa pun penyelarasan terkecil pada mesin/kompiler Anda, dan Num_Array[n] Anda sebenarnya membutuhkan 32n bit karena Anda menggunakan bilangan bulat 32-bit untuk menyimpan nilai Boolean ).

Komentar lain menyarankan Anda menyimpan nilai ini di heap, bukan di stack. std::vector<bool> akan melakukannya untuk Anda secara otomatis.

person Zach    schedule 10.02.2013
comment
Cara penulisan program saya menggunakan tiga variabel dalam array. Yang satu bersifat arbitrer, jadi saya bisa melihat logika di balik array Boolean. Tetapi bagaimana saya menerapkan ini sehingga variabel arbitrer lainnya masih dapat dimasukkan? - Terima kasih - person Nathan J; 10.02.2013
comment
Melihat kode Anda, sepertinya satu-satunya nilai yang Anda periksa atau tetapkan adalah 0 atau 1. Karena setelah memeriksa 1, kode Anda tetap menetapkannya menjadi 0 (tanpa memeriksa 3), saya pikir itu akan memiliki efek yang sama jika Anda menginisialisasi seluruh array ke 0, bukan 3. Kemudian Anda dapat menyimpan semuanya sebagai satu bit. - person Zach; 10.02.2013