大于 200 万的埃拉托色尼筛 [C]

Question

我正在尝试编写一个程序来命名所有不超过 n 的素数。当我输入大于 200 万的数字时，程序崩溃。有人可以帮助我吗？

#include <stdio.h>
#include <math.h>

void sieve(unsigned long long int n, char primes[]);

int main()
{
  unsigned long long int i, n = 2000000; // find the primes up to 500000
  char v[n];
  sieve(n, v);
  for (i=0;i<n;i++)
    if (v[i] == 1)
      printf("%I64u\n",i); // this just prints out each value if it's Prime
}

void sieve(unsigned long long int n, char primes[])
{
  unsigned long long int i, j;
  for (i=0;i<n;i++)
    primes[i]=1; // we initialize the sieve list to all 1's (True)
  primes[0]=0,primes[1]=0; // Set the first two numbers (0 and 1) to 0 (False)
  for (i=2;i<sqrt(n);i++) // loop through all the numbers up to the sqrt(n)
    for (j=i*i;j<n;j+=i) // mark off each factor of i by setting it to 0 (False)
      primes[j] = 0;
}

错误信息：

Process returned -1073741571 (0xC00000FD) execution time : 2.032 s

Answer 1

坚持这个网站的名字；您遇到堆栈溢出。 ;-)

尝试

char *v = malloc(n);

和

void sieve(unsigned long long int n, char *primes)

分别。当然，你还需要

free(v);

除此之外，我还没有检查你的算法是否正确。

Answer 2

问题是因为您的程序没有预留足够的内存，正如@Pedram Azad 所提到的，您有堆栈溢出。您可以通过为您的 var (malloc) 分配更多内存来绕过它。

此外，您需要开始为您的代码块（循环和条件语句）使用方括号。它有助于可视化问题。缩进很混乱。

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

void sieve(unsigned long long int, char *);


int main()
{
  unsigned long long int i, n = 63000000; // find the primes up to 500000
  char *v = (char*) malloc(n*sizeof(char));
  sieve(n, v);
  for (i=0; i<n; i++) {
    if (v[i] == 1) {
      printf("%lld\n",i); // this just prints out each value if it's Prime
    }
  }
  free(v);
}

void sieve(unsigned long long int n, char *primes)
{
  unsigned long long int i, j;
  for (i=0; i<n; i++) {
    primes[i]=1; // we initialize the sieve list to all 1's (True)
  }
  // Set the first two numbers (0 and 1) to 0 (False)
  primes[0]=0;
  primes[1]=0;
  // loop through all the numbers up to the sqrt(n)
  for (i=2; i<sqrt(n); i++) {
    for (j=i*i; j<n; j+=i) {
      // mark off each factor of i by setting it to 0 (False)
      primes[j] = 0;
    }
  }
}

大于 200 万的埃拉托色尼筛 [C]

Sieve of Eratosthenes for higher numbers than 2 Million [C]

c

numbers

function

sieve