CODEWITHSUNDEEP
cprimes
Marlon Vermeulen
Marlon Vermeulen

Reputation: 3

exceeding 500000 with the method of Erastosthenes

i got a problem which i can't solve

I want to know all prime numbers below a given limit x. Allowing me to enter x and calculate the prime numbers using the method of Erastosthenes. Displaying the result on the screen and saving it to a text file.

Calculating the primenumbers below the x, printing them and saving them to a text file worked, the only problem i have is that x can't exceed 500000 could you guys help me?

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

void sieve(long x, int primes[]);

main()
{
    long i;
    long x=500000;
    int v[x];

    printf("give a x\n");
    scanf("%d",&x);

    FILE *fp;

    fp = fopen("primes.txt", "w");
    sieve(x, v);
    for (i=0;i<x;i++)
    {
        if (v[i] == 1)
        {
            printf("\n%d",i);
            fprintf(fp, "%d\n",i);
        }
    }
    fclose(fp);
}

void sieve(long x, int primes[])
{
    int i;
    int j;
    for (i=0;i<x;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(x);i++) // loop through all the numbers up to the sqrt(n)
    {
        for (j=i*i;j<x;j+=i) // mark off each factor of i by setting it to 0 (False)
        {
            primes[j] = 0;
        }
    }

}

Upvotes: 0

Views: 96

Answers (4)

chqrlie
chqrlie

Reputation: 144969

Allocating v as an array of int is wasteful, and making it a local array is risky, stack space being limited. If the array becomes large enough to exceed available stack space, the program will invoke undefined behaviour and likely crash.

While there are ways to improve the efficiency of the sieve by changing the sieve array to an array of bits containing only odd numbers or fewer numbers (6n-1 and 6n+1 is a good trick), you can still improve the efficiency of your simplistic approach by a factor of 10 with easy changes:

  • fix primes[0] and primes[1] outside the loop,

  • clear even offsets of prime except the first and only scan odd numbers,

  • use integer arithmetic for the outer loop limit,

  • ignore numbers that are already known to be composite,

  • only check off odd multiples of i.

Here is an improved version:

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

void sieve(long x, unsigned char primes[]) {
    long i, j;

    for (i = 0; i < x; i++) {
        primes[i] = i & 1;
    }
    primes[1] = 0;
    primes[2] = 1;
    /* loop through all odd numbers up to the sqrt(x) */
    for (i = 3; (j = i * i) < x; i += 2) {
        /* skip composite numbers */
        if (primes[i] == 0)
            continue;
        /* mark each odd multiple of i as composite */
        for (; j < x; j += i + i) {
            primes[j] = 0;
        }
    }
}

int main(int argc, char *argv[]) {
    long i, x, count;
    int do_count = 0;
    unsigned char *v;

    if (argc > 1) {
        x = strtol(argv[1], NULL, 0);
    } else {
        printf("enter x: ");
        if (scanf("%ld", &x) != 1)
            return 1;
    }

    if (x < 0) {
        x = -x;
        do_count = 1;
    }
    v = malloc(x);
    if (v == NULL) {
        printf("Not enough memory\n");
        return 1;
    }

    sieve(x, v);

    if (do_count) {
        for (count = i = 0; i < x; i++) {
            count += v[i];
        }
        printf("%ld\n", count);
    } else {
        for (i = 0; i < x; i++) {
            if (v[i] == 1) {
                printf("%ld\n", i);
            }
        }
    }
    free(v);
    return 0;
}

Upvotes: 1

thesun
thesun

Reputation: 110

You are initializing x to be 500000, then creating an array with x elements, thus it will have 500000 elements. You are then reading in x. The array will not change size when the value of x changes - it is fixed at 500000 elements, the value of x when you created the array. You want something like this:

long x=500000;

printf("give a x\n");
scanf("%d",&x);

int *v = new int[x];

This fixes your fixed size array issue, and also gets it off the stack and into the heap which will allow you to allocate more space. It should work up to the limit of the memory you have available.

Upvotes: 1

gnasher729
gnasher729

Reputation: 52602

You will be able to handle four times as many values by declaring char v [500000] instead of int v [100000].

You can handle eight times more values by declaring unsigned char v [500000] and using only a single bit for each prime number. This makes the code a bit more complicated.

You can handle twice as many values by having a sieve for odd numbers only. Since 2 is the only even prime number, there is no point keeping them in the sieve.

Since memory for local variables in a function is often quite limited, you can handle many more values by using a static array.

Upvotes: 4

Marius Bancila
Marius Bancila

Reputation: 16338

I believe the problem you are having is allocating an array of int if more than 500000 elements on the stack. This is not an efficient way, to use an array where the element is the number and the value indicates whether it is prime or not. If you want to do this, at least use bool, not int as this should only be 1 byte, not 4.

Also notice this 

for (i=0;i<x;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)
}

You are reassigning the first two elements in each loop. Take it out of the loop.

Upvotes: 1

Related Questions