Search code examples
csieve-algorithm

No Output for Prime Sieve


I'm trying to print out a particular set of primes using a sieve, but I just don't seem to get any output yet it all compiles fine. The program doesnt exit unless I force it, so I'm guessing its stuck somewhere...How can I fix this?

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

int64_t* prime_vector(int64_t start);

int64_t* prime_vector(int64_t start) {

    int64_t* vector = calloc(7,sizeof(int64_t));

    int64_t maxnum = 2000000;

    int64_t *isprime = calloc(maxnum, sizeof(int64_t));

    for (int i=0; i < maxnum; i++){
        isprime[i] = 1;
    }

    for (int64_t i=0; i*i < maxnum; i++){
        if (isprime[i]){
            for (int64_t j = i*i; j<maxnum; j+=i){
                isprime[j] =0;
            }

        }

    }

    int64_t count = 0;
    int64_t max = 7;
    int64_t number = start;
    int64_t j = 0;


    for (int64_t i = number; i<maxnum;i++){
        if (count < max && isprime[i]){
            vector[j] = i;
            count++;
            j++;
        }

    }
    free(isprime);
    return vector;

}


int main (void){

    int64_t* array = prime_vector(13);

    for (int i=0; i<7; i++){
            printf("%d\n",array[i]);
    }

    return 0;

}

Solution

  • You have an infinite loop - when your outer loop i = 0 then the inner loop increment j+=i will not increment at all.

     for (int64_t i=0; i*i < maxnum; i++){
            if (isprime[i]){
                for (int64_t j = i*i; j<maxnum; j+=i){
                    isprime[j] =0;
                }
            }
        }
    

    Given that zero and 1 are not primes, I would assign these as isprime[] = 0 and start off i at 2.