CODEWITHSUNDEEP
cfunctionnumberssieve-algorithm
Nord
Nord

Reputation: 7

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

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

Upvotes: 0

Views: 218

Answers (2)

renno
renno

Reputation: 2827

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

Upvotes: 1

Pedro
Pedro

Reputation: 862

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.

Upvotes: 1

Related Questions