Eratosthenes 素数筛达一百万 C++

Question

所以我的代码需要帮助。出于某种原因，当我输入超过 500,000 的数字时，它会一直崩溃。这是确切的任务。

Implement the Sieve of Eratosthenes and use it to find all prime numbers less than or equal to one million. Use the result to prove Goldbach's Conjecture for all even integers between four and one million, inclusive.

Implement a function with the following declaration:
void sieve(int array[], int num);
This function takes an integer array as its argument. The array should be initialized to the values 1 through 1000000. The function modifies the array so that only the prime numbers remain; all other values are zeroed out.

This function must be written to accept an integer array of any size. You must should output for all primes numbers between 1 and 1000000, but when I test your function it may be on an array of a different size.

Implement a function with the following declaration:
void goldbach(int array[], int num);
This function takes the same argument as the previous function and displays each even integer between 4 and 1000000 with two prime numbers that add to it.

The goal here is to provide an efficient implementation. This means no multiplication, division, or modulus when determining if a number is prime. It also means that the second function must find two primes efficiently.

Output for your program:

All prime numbers between 1 and 1000000 and all even numbers between 4 and 1000000 and the two prime numbers that sum up to it.

DO NOT provide output or a session record for this project!

这是我目前所掌握的。如果有人可以帮助我，那就太好了。

#include <iostream>
using namespace std;

void sieve (int array[], int num);

int main()
{
    int num;
    cout << "Enter a number to calculate up to." << endl;
    cin>> num;
    if ( num < 2 )
        return 0;

    int array[num];
    array[0]= array[1]= 0;
    for ( int i= 2; i < num; ++i )
        array[i]= i;
    sieve(array,num);
    for (int i=0; i<num; i++)
        if (array[i] > 0)
            cout << array[i] <<" "<<endl;
    cout<<endl;

    return 0;
}

void sieve( int array[], int num )
{
    for ( int i= 0; i < num; ++i )
    {
        if ( array[i] != 0 )
        {
            for ( int j= i+i; j < num; j += i )
            {
                array[j]= 0;
            }
        }
    }
}

Answer 1

您的代码崩溃的原因是您在此处为数组使用了 VLA 分配

int array[num];

它用于分配堆栈的 num 个 int 元素，这很可能太小而无法容纳一百万个 int 值。

您应该注意到它不是标准的 c++ 功能，而是许多编译器实现提供的扩展。

要解决这个问题，有三种选择：

您将用于程序的堆栈大小配置为足够大以容纳 int 个元素（这是 OS 依赖项）
您使用 std::vector<int> array(num); 代替，它在堆内存上分配这些元素
您在程序末尾使用 int* array = new int[num]; 和 delete [] array; 自己在堆上分配必要的内存（我不推荐此解决方案，因为它很容易在有关适当的内存管理）

Answer 2

我看到这是一个作业，你需要编写自己的代码，但我有一些想法可以显着减少内存量。

为什么不使用位数组来代替？

做类似的事情

#define IS_SET(x) (arr[(x)>>3] & (0x01 << ((x) & 0x07)))
#define SET(x) (arr[(x)>>3] |= (0x01 << ((x) & 0x07)))

并将 arr 定义为 char 的数组。这将使内存利用率降低 8 倍。对于 C++，您可以使用 bool 可能不会让您获得尽可能低的内存使用量。

首先清除所有的char元素。然后使用 SET(x) 为每个数字设置位，完成一次所有标记。如果 IS_SET(x) 的计算结果为假，那么 x 是素数。

节省大量内存。

编辑 1：

另一个减少 50% 所需内存的技巧是不为偶数保留 space。从 i=3 开始，始终使用 i+=2 递增并标记位数组。阅读时也这样做。

EDIT2:

如果你能找到一个序列来跳过整数的倍数，即二或三或两者的倍数，那么你可以多节省大约 30% 的内存。事实上，您可以制作这样一个系列，并跳过存储和标记二和三或两者的倍数。

Eratosthenes 素数筛达一百万 C++

Sieve of Eratosthenes prime numbers up to a million c++

c++

sieve-of-eratosthenes