Home > Software design >  Non-deterministic output of simple C program
Non-deterministic output of simple C program

Time:11-15

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

CodePudding user response:

In C, a local array is not initialized, probably for performance reasons.

One way to fix this is to loop over it to set each element to false.

CodePudding user response:

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.

  • Related