Prime Generator ล้น? ซี++

ฉันกำลังเขียนเครื่องกำเนิดจำนวนเฉพาะโดยใช้ตะแกรงเอราทอสเทนีส ฉันทำให้มันทำงานในการสร้างจำนวนเฉพาะที่ต่ำกว่า 521102 ได้ แต่ตัวเลขที่สูงกว่านี้จะทำให้โปรแกรมหยุดทำงาน นี่คือรหัสของฉัน

#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;
}

ฉันใส่ MAX_NUM เป็น 1000000 และมันใช้งานไม่ได้ แต่อย่างที่ฉันบอกไปก่อนหน้านี้ ตัวเลขที่ต่ำกว่า 521102 ก็ใช้ได้ ฉันต้องสามารถทดสอบตัวเลขที่สูงขึ้นได้ ปัญหาของฉันคืออะไร และฉันจะแก้ไขได้อย่างไร

ขอบคุณมาก!

ขอบคุณสำหรับการตอบรับ ฉันลองวิธีแก้ปัญหาการจัดสรรอาเรย์แบบไดนามิก มันทำงานได้ดีในระดับหนึ่ง หลังจากตั้งค่า MAX_NUM เป็นประมาณ 500 ล้าน ฉันได้รับข้อผิดพลาดนี้เมื่อฉันเรียกใช้โปรแกรม...

ยุติการเรียกหลังจากโยนอินสแตนซ์ของ 'std::bad_alloc' what(): std::bad_alloc

แอปพลิเคชันนี้ได้ขอให้ Runtime ยุติการทำงานด้วยวิธีที่ผิดปกติ โปรดติดต่อทีมสนับสนุนของแอปพลิเคชันเพื่อขอข้อมูลเพิ่มเติม

มีหลังคา 500 ล้านก็ใกล้จะรับได้ แต่สูงกว่านี้จะดีกว่าไหม? มีความคิดอื่นอีกไหม?


c++ arrays overloading generator
person Nathan J    schedule 10.02.2013    source แหล่งที่มา
comment
เส้นไหนที่ทำให้เกิดการชนกันแน่?   -  person Peter L.    schedule 10.02.2013
comment
คุณอาจใช้งานบน Windows และอาจเกินขีดจำกัดสูงสุดบนสแต็ก จัดสรรอาร์เรย์แบบไดนามิกหรือจัดสรรแบบคงที่ (อาจอยู่นอกฟังก์ชัน) หรือค้นหาวิธีเพิ่มขนาดสแต็ก   -  person Jonathan Leffler    schedule 10.02.2013
comment
นี่ไม่ใช่ปัญหา แต่สำนวนสำหรับการใช้ int แบบยาวคือการประกาศง่ายๆ ว่า long   -  person Pete Becker    schedule 10.02.2013

คำตอบ (3)


arrow_upward
3
arrow_downward

สมมติว่าคุณใช้ Windows สแตกของคุณมีขนาดเล็กเกินไป (โดยค่าเริ่มต้น 1MB) เพื่อให้พอดีกับตัวแปรต่อไปนี้ในเฟรมสแต็ก:

int Num_Array [MAX_NUM_ARRAY];

คุณควรจัดสรรมันลงในฮีป:

int *Num_Array = new int[MAX_NUM_ARRAY];
...
delete[] Num_Array;
person JosephH    schedule 10.02.2013
comment
คุณควรจัดสรรมันลงในฮีป - ทำไม? หน่วยความจำเริ่มต้น (DATA หรือ BSS) ไม่ (ไม่) ดีเพียงพอหรือไม่ - person ; 10.02.2013
comment
@ H2CO3 แก้ไขฉันให้ถูกต้องหากฉันผิด แต่ฉันคิดว่านั่นจะเป็นการเพิ่มขนาดของไฟล์ปฏิบัติการโดยไม่จำเป็นใช่ไหม - person JosephH; 10.02.2013
comment
หากคุณมีความอยากอาหารจากสงครามการเพิ่มประสิทธิภาพก่อนเวลาอันควร: ทำไมจะไม่ได้ล่ะ? มันอาจเพิ่มขนาดปฏิบัติการได้ แต่จะเร็วขึ้นด้วยเนื่องจากมีที่อยู่คงที่ - person ; 10.02.2013
comment
@ H2CO3 โอ้ฉันเดาว่าเราทั้งคู่คงเห็นพ้องกันว่าเราสามารถจัดสรรมันในฮีประหว่างการเริ่มต้นได้ - person JosephH; 10.02.2013
comment
@JoesphH เพียงเพื่อให้ชัดเจน: ท้อแท้ในการจัดสรรข้อมูลสแตติกแบบฮีปซึ่งมีชีวิตอยู่ตลอดอายุการใช้งานของโปรแกรม - person ; 10.02.2013
comment
@ H2CO3 นี่เริ่มไร้สาระ มันสร้างความแตกต่างอะไรในโค้ดที่ OP ให้มา? - person JosephH; 10.02.2013

arrow_upward
1
arrow_downward

อาจเป็นเพราะคุณกำลังทุบกอง แล้วการย้ายอาร์เรย์ออกจากฟังก์ชัน 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

ข้อเท็จจริงที่ว่าคุณใช้ std::fill_n บ่งบอกว่าคุณกำลังเขียน C++ ไม่ใช่ C

คุณสามารถลดการใช้หน่วยความจำของโปรแกรมของคุณได้อย่างมากโดยใช้อาร์เรย์บูลจริงแทนอาร์เรย์ int เนื่องจากคุณใช้ C++ คุณสามารถรับอาร์เรย์บูลีนได้โดยใช้ std::vector<bool> ต่างจาก bool[n], std::vector<bool>(n) ใช้เพียง n บิต (bool[n] อาจใช้ถึง 8n บิต หรืออะไรก็ตามที่มีการจัดตำแหน่งที่เล็กที่สุดบนเครื่อง/คอมไพเลอร์ของคุณ และ Num_Array[n] ของคุณใช้ 32n บิตจริงๆ เนื่องจากคุณใช้จำนวนเต็ม 32 บิตในการจัดเก็บค่าบูลีน ).

ความคิดเห็นอื่น ๆ แนะนำให้คุณเก็บค่านี้ไว้ในฮีปแทนที่จะเก็บไว้ในสแต็ก std::vector<bool>จะทำสิ่งนั้นให้คุณโดยอัตโนมัติ

person Zach    schedule 10.02.2013
comment
วิธีเขียนโปรแกรมของฉันใช้ตัวแปรสามตัวในอาร์เรย์ อันหนึ่งเป็นแบบใดก็ได้ ดังนั้นฉันจึงสามารถเห็นตรรกะเบื้องหลังอาร์เรย์บูลีนได้ แต่ฉันจะนำสิ่งนี้ไปใช้อย่างไรเพื่อให้สามารถรวมตัวแปรที่กำหนดเองอื่น ๆ ไว้ได้ - ขอบคุณ - person Nathan J; 10.02.2013
comment
เมื่อดูโค้ดของคุณ ดูเหมือนว่าค่าเดียวที่คุณตรวจสอบหรือตั้งค่าไว้คือ 0 หรือ 1 เนื่องจากหลังจากตรวจสอบ 1 แล้ว รหัสของคุณก็จะตั้งค่าเป็น 0 ต่อไป (โดยไม่ตรวจสอบ 3) ฉันคิดว่ามันจะมีผลเช่นเดียวกันหาก คุณเริ่มต้นอาร์เรย์ทั้งหมดเป็น 0 แทนที่จะเป็น 3 จากนั้นคุณก็สามารถจัดเก็บทุกอย่างเป็นบิตเดียวได้ - person Zach; 10.02.2013