1

I'm trying to create a program which will print out all the prime numbers between two numbers using the Sieve or Eratosthenes. I'm trying to follow the pseudocode on the website, but i'm slightly stuck on the first bit which says:

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

I've tried doing this and I came up with this: (I was going to use #DEFINE but the range at which the prime numbers will be printed at will be based on user input so different each time)

bool *prime = malloc((number1-1) * sizeof(*prime));

However I think this only sets the size and not the actual values in the array.

I did some research on this already and found similiar questions on here, but they were all for different programming languages.

MichaelJonnu
  • 31
  • 1
  • 3
  • Whats wrong with just doing a for loop to initialize all of the values? – John3136 Nov 06 '18 at 11:40
  • @John3136 just a For loop to do what? – MichaelJonnu Nov 06 '18 at 11:41
  • 2
    Should be `sizeof(*prime)` is `prime` is a pointer. – Paul Ogilvie Nov 06 '18 at 11:42
  • 1
    In C everything that is non-zero is considered "true". So you could easily use e.g. [`memset`](https://en.cppreference.com/w/c/string/byte/memset) to set each byte in an array to non-zero. – Some programmer dude Nov 06 '18 at 11:42
  • @Someprogrammerdude I tried using memset already and it was giving me an error – MichaelJonnu Nov 06 '18 at 11:43
  • 1
    Then please *show* us what you've tried (preferably in the form of a [Minimal, Complete, and Verifiable Example](http://stackoverflow.com/help/mcve)), and tell us *how* it failed. Also please read about [how to ask good questions](http://stackoverflow.com/help/how-to-ask), as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). – Some programmer dude Nov 06 '18 at 11:44
  • @MichaelJonnu how did you try and what type of error you get? – kurtfu Nov 06 '18 at 11:44
  • *an array [...] indexed by integers 2 to n* **2** to n? Why starting with 2? – Cid Nov 06 '18 at 11:51
  • @Cid 0 and 1 are not treated as prime numbers and the program will be to find prime numbers, so I guess it doesn't use them from the start – MichaelJonnu Nov 06 '18 at 11:52

2 Answers2

3

You can use memset. Usually 1 is defined as true and 0 as false.

memset(prime,1,n * sizeof(*prime));

Another method is to use a for loop to initialize the array to 1

#include <stdbool.h>
for (int i=0; i<n; i++)
{
    prime[i] = true;   
}
Rishikesh Raje
  • 8,556
  • 2
  • 16
  • 31
  • memset takes the size in bytes as argument, therefore you should pass `n * sizeof *prime`, since I think it is not guaranteed that `sizeof (bool)` is `1`. – Osiris Nov 06 '18 at 11:49
  • 2
    In the explicit loop, please use `true` instead of `1`. – Some programmer dude Nov 06 '18 at 11:49
  • @RishikeshRaje i've done it like this: bool prime[number1+1] memset(prime, 1,n * sizeof(prime)); Would this be correct or would it give errors? – MichaelJonnu Nov 06 '18 at 12:04
  • @MichaelJonnu - looks like an equal is missing in that statement. Also if you are setting the bool array of size `number+1` then the memset should be also of the same size. Also, a variable size object in C99 cannot be initiaized. So the operations should be on two lines. – Rishikesh Raje Nov 07 '18 at 04:54
2

First off, memset can be used to set a range of bytes to any value, so:

memset(prime, '\xff', (number1-1) * sizeof(*prime));

should set all bits to 1 in the array; any non-zero value is true, and \xff is the byte pattern of all 1s, so it's as truthy as any other non-zero value.

It looks like memset may be inappropriate here, so the only unambiguously correct solution with no changes to program logic is a straight loop:

for (size_t i = 0; i < number1-1; ++i) {
    primes[i] = true;
}

That said, there is a slightly more clever way to do this: Reverse the definition of the array. Instead of the array being true when prime, make it true when not prime. That way, initialization can simplify to:

bool *notprime = calloc(number1-1, sizeof(*prime));

Now you can benefit from the cheap zeroing calloc typically provides (when sieving large enough ranges that the OS is tapped for already zeroed memory) and avoid the need to initialize them to some other value at all.

Note: When you allocated the array, you wanted sizeof(*prime), not sizeof(prime); I fixed that in the equivalent calloc call.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • Note that `'\xff'` is equal to `0xff`. And consider that `true` from [``](https://en.cppreference.com/w/c/types/boolean) is `1` which makes a comparison like `notprime[i] == true` *false*. – Some programmer dude Nov 06 '18 at 11:47
  • 1
    @Someprogrammerdude: Whenever I see someone writing code that compares to `true`, instead of just testing it, I'm saddened (since it's usually wrong, as in this case). In any event, there is no guarantee that `bool` is a single byte in size either, so `memset` wouldn't work no matter what byte value you used if you compared to `true` directly. – ShadowRanger Nov 06 '18 at 11:48
  • So I'd imagine that if I use calloc, the algorithm for actually finding out the primes would change as well/be reversed, as the array is now for non primes? – MichaelJonnu Nov 06 '18 at 11:50
  • @MichaelJonnu: Yup. Most of the changes would just be strategic insertions of `!` to reverse tests though; it's not a major change. – ShadowRanger Nov 06 '18 at 11:51
  • `true` explicitly has the value `1` in C. Therefore this solution is not correct and memset cannot be used. However, if you convert from this binary goo to `bool`, you will get the value 1 if you type `bool b = prime[n];`. But you cannot treat `prime[n]` as a boolean by itself, and `prime` cannot be an array of boolean. – Lundin Nov 06 '18 at 11:55
  • @Lundin: Does it matter if all your tests are `if (prime[i])`? I'm sure `true` itself has a specific value, but code that actually tests equality with `true` is usually considered non-idiomatic. If the standard forbids it, so be it, but I'm not generally concerned with being exactly `true`, merely "truthy". In any event, in the actual Eratosthenes code I've written, I've always used the second approach (with `calloc`), because for large arrays, it makes a meaningful difference on runtime to not need to perform initialization at all. Of course, in real code, I use bit flags for memory savings. – ShadowRanger Nov 06 '18 at 11:58
  • There's plenty of cases where it might fail, beyond explicit checks against `true`. `bool array[3] = {true, true, true}; ... memcmp(array, prime, sizeof(bool)*3);` Worse yet, by mallocing a bool array and then setting the values you memset, the array does not yet have an effective type. My interpretation of the standard is that by writing to it with memset, you force the effective type to become `unsigned char`. And so subsequent access to the array using a `bool*` might be undefined behavior. I'm not certain, but I would avoid relying on fishy corner cases of the standard. – Lundin Nov 06 '18 at 12:11
  • I posted a language-lawyer question since this is a peculiar special case. https://stackoverflow.com/questions/53171804/is-it-well-defined-to-use-memset-on-a-dynamic-bool-array – Lundin Nov 06 '18 at 12:21
  • @Lundin: Regardless of how that question turns out, it looks like `memset` is at best ambiguously correct (no matter what the chosen value is, given `_Bool` has no size constraints), so I've crossed out that recommendation in favor of a plain loop (or as previously noted, a `calloc` that gets simpler code and better performance for large allocations). – ShadowRanger Nov 06 '18 at 13:38