在没有参数的函数中生成一个新素数

Question

我正在做一个问题，我需要创建一个不带参数的函数 generatePrime。函数第一次调用时应return数2，3（第二次），5（第三次）等。

我有一种直觉，这应该用递归来完成。但是我不确定如何制作没有参数的递归函数。

不过，这只是程序的一部分 - 整个程序本身应该 return 在一些 low 和 high 数字之间（不包括它们）

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

如果作业确实需要您编写一个不带参数的函数，并且 return 每次调用都是一个连续的素数，那么您可能打算使用静态对象。以下是 return 一个简单计数器的实现方法：

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

使用类似的静态对象可以实现一个例程，该例程将 return 从 2 开始的连续素数。但是，如果它必须以用户提供的 low 值开头，则有以下三种选择：

low 值必须以某种方式传递给函数。如果不是作为参数，那么它必须通过函数和调用者都可以访问的某个对象，例如在任何函数外部声明的变量。这通常被认为是糟糕的设计，不是一个好的编程任务。
该函数可以使用其静态对象来了解它何时被第一次调用，并且可以在该实例中从输入中读取低值并记住它（通过静态对象）。
main 例程可以重复调用 GenerateCounter，并且只有在达到 low 值后才开始打印其结果。这很浪费，而且不太可能是作业的目的。

Answer 2

创建一个没有参数的递归函数没有多大意义，因为递归的全部意义在于函数参数随着递归的每一级而变化。

如果您希望函数 generatePrime 不带任何参数，但每次调用时都会 return 下一个素数，那么函数必须记住它 return 的最后一个值编辑。这可以通过在具有 static storage duration 的变量中记住此值来实现，例如全局变量或 static 局部变量。由于您需要从函数 main 和函数 generatePrime 访问此变量，我建议使用全局变量。

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

这个程序有以下输出：

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

注意这个程序会计算出比它打印出来的多一个质数，这有点浪费。但是，由于您的任务要求函数 generatePrime 不带任何参数，因此我看不到任何简单的方法来解决此问题。

Answer 3

... should return primes between some low and high

这里真的不需要递归。把这个想法放在一边。

创建 table [0...high] 并应用 Sieve of Eratosthenes。因此，第一步确定所有寻求的素数。

// 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

创建一个无参数函数，它遍历已完成的 table 从低位开始寻找仍然是质数的条目。

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

这将是形成素数的一种非常快速的解决方案[低...高]。缺点：代码需要组成一个大数组。

在没有参数的函数中生成一个新素数

Generating a New Prime in Function without Parameters

c

recursion

primes

for-loop

function