coutputprimesnon-deterministic

Non-deterministic output of simple C program


This is an unfinished program I'm writing to learn C (only checks multiples of 2 currently...)

Ultimately, I want this to be an implementation of the Sieve of Eratosthenes (prime numbers)

The problem I'm having is that the output is non-deterministic: sometimes the output includes 11, other times it does not - This happens for a handful of numbers. I have experimented by changing a few things, such as actually initializing the array of booleans to false.

Any ideas why this might be happening?

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

int main(int argc, char *argv[]) {
        int n = atoi(argv[1]);
        int initialPrimeIterator = 2;
        _Bool compositePrimeNumbers[n];

        printf("Prime Numbers from 2 -> %d\n", n);
        for (int i = initialPrimeIterator; i < n; i += initialPrimeIterator) {
                compositePrimeNumbers[i-1] = true;
        }
        printf("Done...\n");
        
        printf("Printing prime numbers from 2-> %d\n", n);
        for (int i = 2; i < n; i++) {
                if (!compositePrimeNumbers[i]){
                        printf("%d\n", i + 1);
                }
        }
        
        return 0;
}

edit: haha. Just realized I have an array named 'compositePrime...' Should just be 'compositeNumbers'


Solution

  • Since I understand you are aiming at completing the program when overcoming this hurdle, I will not post a completed program, but only point out issues in your current version:

    1. As it has been noted, the array compositePrimeNumbers is uninitialized. Since it must be initialized with all values false which is represented by 0, the quickest way is this:
         memset(compositePrimeNumbers, 0, sizeof(compositePrimeNumbers));
    
    1. You should not mark the current initialPrimeIterator as a composite number, hence the for-loop should start with the next multiple. Also, n must be included:
        for (int i = 2 * initialPrimeIterator; i <= n; i += initialPrimeIterator) {
    

    (actually, this can be optimized by replacing 2 * initialPrimeIterator with initialPrimeIterator * initialPrimeIterator).

    With these changes, I believe you are well on the way to complete the program.