1

I'm completely new to C, only really having had experience with Python in the past, so please forgive my ignorance here.

I'm trying to implement the prime-sieve algorithm of Eratosthenes in C. This algorithm recursively discards all multiples of a given number until the last number you wish to know is found. Specifically, the program will have an input n, and will output all prime numbers smaller than n.

To achieve this, I thought to create an array of length n and recursively cycle over this array, discarding integers I no longer care about (by changing them to 0).

The problem I found however, is that c does not allow for an array of variable length. I thought I outsmarted this rule for a little bit by doing this trick:

void Sieve(int n) {
    int prime[n+1];
}

But sadly, even variables given to functions aren't okay.

Hence my question: How can I initiate such an array in C?

Mitchell Faas
  • 430
  • 6
  • 19
  • 4
    Any C99 compliant compiler should support VLAs. (variable-length-arrays). Which compiler are you using? – bool3max Sep 24 '18 at 13:13
  • 2
    Modern C allows variable length arrays, but apparenty your C compiler is older. Use dynamic memory allocation (`malloc` and friends), your C textbook contains all necessary information. But even with VLAs you'll run into problems for large values of `n` because on most implementation VLAs are allocated on the stack which has limited capacity (typically a few megabytes) – Jabberwocky Sep 24 '18 at 13:13
  • 1
    Like what **Jabberwoky** said, use `malloc`: `int prime[] = malloc(sizeof(int) * (n + 1));` – absoluteAquarian Sep 24 '18 at 13:13
  • 4
    @Tau, no it's `int *prime = malloc(...`, not `int prime[] = malloc(...`. – Jabberwocky Sep 24 '18 at 13:14
  • @Tau that's an invalid array initializer – bool3max Sep 24 '18 at 13:14
  • @bool3max I'm using a recent version of gcc. I'm getting the error in visual studio, which I only use to write the code. – Mitchell Faas Sep 24 '18 at 13:16
  • 2
    Ah, Visual Studio insists on using a C89 compiler. – Reticulated Spline Sep 24 '18 at 13:17
  • Ah, apologies. I had forgotten. – absoluteAquarian Sep 24 '18 at 13:18
  • "How can I initiate such an array in C?" --> variable length arrays (VLA) cannot be _initialized_. The elements can be _assigned_ though. – chux - Reinstate Monica Sep 24 '18 at 13:30
  • @chux I understand you're trying to help my understanding of C, but like I said: I'm completely new to this language. Though you now taught me that there is a difference, I still wouldn't know what the difference would be. (I'm going to look this up, but in the future you might want to define your terms ^^) – Mitchell Faas Sep 24 '18 at 13:42
  • look into *segmented* sieve of Eratosthenes. to get to a prime `p` you only need to know the primes up to its square root. also loops are better than recursion in C, AFAIK. – Will Ness Sep 24 '18 at 13:59
  • 1
    The C compiler of Visual Studio 2017 is ancient, most of it is from the early 1990s. Replace it with a modern C compiler. – Lundin Sep 24 '18 at 14:15
  • When you compile with GCC, be sure to specify `-std=C99` or `-std=C11` (or `-std=C90`). Without this, GCC compiles GNU C, a language similar to but not the same as ISO Standard C. For useful diagnostics you should also use `-pedantic -Wall -Wextra`. – mlp Sep 24 '18 at 15:07
  • @MitchellFaas, To help discern the difference in C terminology, some search links: [initialize](https://www.google.com/search?client=safari&rls=x64&q=c++initialize&ie=UTF-8&oe=UTF-8) and [assign](https://en.wikipedia.org/wiki/Assignment_operator_(C%2B%2B)). – chux - Reinstate Monica Sep 24 '18 at 17:39

1 Answers1

2

You can use dynamic memory allocation:

int* prime;
prime = malloc(sizeof(int)*n);

then use it as a regular array e.g. prime[n-1]

Sandy
  • 895
  • 6
  • 17
  • you may want to cast to int* the return value of the malloc: prime = (int*)malloc(sizeof(int)*n); – Alexander James Pane Sep 24 '18 at 13:19
  • 4
    @AlexanderPane we do not [cast the result of malloc](https://stackoverflow.com/q/605845/1606345) in C – David Ranieri Sep 24 '18 at 13:20
  • @KeineLust I agree with you. But doesn't casting increase the code portability and also gives the possibility to compile with a C++ compiler? But if this is not required, I agree that it is not useful – Alexander James Pane Sep 24 '18 at 13:23
  • 2
    `prime = malloc(sizeof *prime * n);` has advantages of not having to code the type. – chux - Reinstate Monica Sep 24 '18 at 13:29
  • 1
    @AlexanderPane It is portable, because it is standard C and C is not C++. If you want to allocate something in C++, use new. – hellow Sep 24 '18 at 13:32
  • I would go with [`calloc`](https://linux.die.net/man/3/calloc) instead, because you need to initialize your members with 0 anyway. `prime = calloc(sizeof(*prime), n);` – hellow Sep 24 '18 at 13:34
  • 3
    @AlexanderPane: The cast is unnecessary, and just adds to the maintenance burden if you change the type of the target (say from `int` to `long`). Actually, you can do it without exposing type at all - `prime = malloc( sizeof *prime * n );`. I understand why people want to be able to compile the same source as C or C++, but honestly that's a mistake. C and C++ have different rules, and programs that compile as both C and C++ may have subtly different behavior. If you're writing C++, you shouldn't be using C-style memory management *at all* unless you really need to get your hands dirty. – John Bode Sep 24 '18 at 13:46
  • @Hellow There is no need to initialize your members to 0. I initialize the entire array to its index instead since that seems to be the easiest for continued calculation. – Mitchell Faas Sep 24 '18 at 13:51
  • @MitchellFaas You don't really need to store the numbers in the array itself. You only need to store a boolean flag to indicate whether the number has been sieved out yet. If you want to be really clever, you can pack several of those boolean flags into a single integer to save memory. – Ian Abbott Sep 24 '18 at 16:44