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

0

I am trying to make a program which names all prime numbers up to n. When I enter numbers > 2 Million, the program crashes. Can someone help me?

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

Error message:

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

c
function
numbers
sieve
asked on Stack Overflow Nov 29, 2017 by Nord • edited Nov 29, 2017 by tupan

2 Answers

1

Stick to the name of this website; you are experiencing a stack overflow. ;-)

Try

char *v = malloc(n);

and

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

respectively. Of course, you will also need

free(v);

Apart from that, I haven't checked your algorithm for correctness.

answered on Stack Overflow Nov 29, 2017 by Pedro • edited Nov 29, 2017 by Pedro
1

The problem is because your program did not have enough memory reserved and as mentioned by @Pedram Azad you had an stack overflow. You can by-pass that by allocating more memory to your var (malloc).

Also, you need to start using brackets for your code blocks (loops and conditional statements). It helps to visualize problems. The indentation was very confusing.

#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;
    }
  }
}
answered on Stack Overflow Nov 29, 2017 by tupan • edited Nov 29, 2017 by tupan

User contributions licensed under CC BY-SA 3.0