筛选埃拉托色尼素数高达一百万c

Question

所以我的代码需要帮助。由于某种原因，当我输入超过500,000的数字时，它总是崩溃。这是确切的分配。

实现埃拉托斯特尼筛，并用它来查找所有小于或等于一百万的素数。使用结果来证明哥德巴赫猜想对于 400 万到 100 万之间的所有偶数（包括 100 万）。

使用以下声明实现函数：

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

此函数采用整数数组作为其参数。数组应初始化为值 1 到 1000000。该函数修改数组，以便仅保留质数;所有其他值均归零。

必须将此函数编写为接受任何大小的整数数组。您必须输出 1 到 10000000 之间的所有素数，但是当我测试您的函数时，它可能位于不同大小的数组上。

使用以下声明实现函数：

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

此函数采用与前一个函数相同的参数，并显示4到1000000之间的每个偶数整数，其中包含两个质数。

这里的目标是提供高效的实现。这意味着在确定一个数字是否为素数时，没有乘法、除法或模。这也意味着第二个函数必须有效地找到两个素数。

程序的输出：

1到1000000之间的所有质数，4到1000000之间的所有偶数，以及总和的两个质数。

请勿为此项目提供输出或会话记录！

这是我目前所知道的。如果有人能帮我，那就太好了。

#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

匿名用户

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

为什么不使用位数组呢？

做一些像

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

并将arr定义为字符的数组。这将使内存利用率降低8倍。对于C语言，您可以使用bool可能无法获得尽可能低的内存使用率。

首先清除所有char元素。然后对于每个数字集位，使用SET（x）一次完成所有标记。如果IS_SET（x）评估为false，则x是素数。

节省大量内存。

编辑1：

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

编辑2：

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

Answer 2

代码崩溃的原因是您在这里对数组使用了VLA分配

int array[num];

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

您应该注意，它不是标准的c特性，而是由许多编译器实现提供的扩展。

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

1. 您将用于程序的堆栈大小配置为足够大以容纳int元素的数量（这是操作系统依赖的）
2. 您使用标准：：矢量