Generating a New Prime in Function without Parameters

Question

I'm doing a problem where I'm required to make a function generatePrime without parameters. The function should return number 2 when called for the first time, 3 (second time), 5 (third time) and so on.

I have an instinct this should be done with recursion. But I'm not sure how to make a recursive function without parameters.

---

This is only a part of the program, though - the whole program itself should return primes between some low and high numbers (excluding them)

int main(){
int low, high, i;
scanf("%d %d", &low, &high); // Boundaries of interval (low, high)
...
for (i = low + 1; i < high; i++){...}
...
};

int generatePrime(){
...}

Answer 1

If the assignment truly requires you to write a function with no parameters that returns a successive prime on each call, you are probably intended to use a static object. Here is how it can be done to return a simple counter:

int GenerateCounter(void)
{
    static int counter = 0;
    return counter++;
}

Using a similar static object could implement a routine that would return successive primes starting with two. However, if it must start with a low value that is provided by the user, there are three choices:

• The low value must be passed to the function in some way. If not as an argument, then it must be through some object accessible to both the function and the caller, such as a variable declared outside any function. This is generally considered bad design and is not a good programming assignment.
• The function could use its static object to know when it is called for the first time and could, on that instance, read the low value from input and remember it (via the static object).
• The main routine could call GenerateCounter repeatedly and only start printing its results once the low value is reached. This is wasteful and not likely what was intended for the assignment.

Answer 2

Creating a recursive function with no parameters does not make much sense, because the whole point of recursion is that the function arguments change with every level of recursion.

If you want the function generatePrime to take no parameters, but to return the next prime whenever it is called, then the function must remember the last value that it returned. This can be accomplished by remembering this value in a variable with static storage duration, for example a global variable or a static local variable. Since you need to access this variable both from the function main and from the function generatePrime, I recommend a global variable.

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

static int next;

//This function returns true if the number is prime,
//otherwise false. This is a very simple, inefficient
//implementation. Better, more efficient algorithms exist,
//such as the Sieve of Eratosthenes.
bool isprime( int num )
{
    if ( num < 2 )
        return false;

    int max = (int)sqrt( num ) + 1;

    if ( max >= num )
        max = num - 1;

    for ( int i = 2; i <= max; i++ )
    {
        if ( num % i == 0 )
            return false;
    }

    return true;
}

int generatePrime()
{
    while ( !isprime( next ) )
        next++;

    return next++;
}

int main( void )
{
    int low, high, i;

    printf( "Please enter low and high value: " );

    if ( scanf("%d %d", &low, &high) != 2 )
    {
        printf( "invalid input!\n" );
        exit( EXIT_FAILURE );
    }

    next = low + 1;

    while ( ( i = generatePrime() ) < high )
        printf( "%d\n", i );
}

This program has the following output:

Please enter low and high value: 2 30
2
3
5
7
11
13
17
19
23
29

Please enter low and high value: 100 200
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199

Note that this program will calculate one more prime number than it prints, which is a bit wasteful. However, since your task requires the function generatePrime to not take any parameters, I don't see any simple way to fix this.

Answer 3

... should return primes between some low and high

Recursion is not really needed here. Set that idea aside.

Create a table [0...high] and apply the Sieve of Eratosthenes. All the sought after primes are thus determined as a first step.

// Pseudo code
Form table [0... high], mark all true
table[0] = table[1] = false
Set prime = 2
while (prime <= high/prime) {
  for (p=2*prime, p <= high, p += prime)
    mark table[p] = false
  starting at prime, walk list looking for next prime

Create a parameter-less function that walks the completed table starting at low looking for entries that are still prime.

int low, high;

int generatePrime(){
  static int current_prime;
  static char *table  = NULL;
  if (table == NULL) {
    table = malloc(high + 1);

    // Realize pseudo code discussed above here.
    // ...

    current_prime = low - 1;
  }
  // Find next prime
  while (!table[++current_prime]) {
    ;
  }
  return current_prime;
}

---

This will be a very fast solution to forming primes [low ... high]. Downside: code needs to form a large array.