找出数字是否为质数时，递归迭代方法是否比纯迭代方法更好？

Question

我用C语言编写了该程序，用于测试数字是否为质数。我还不了解算法的复杂性以及所有有关Big O的知识，因此我不确定将迭代和递归相结合的方法是否比使用纯迭代方法更有效。

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

typedef struct primenode{
    long int key;
    struct primenode * next;
}primenode;

typedef struct{
    primenode * head;
    primenode * tail;
    primenode * curr;
    unsigned long int size;
}primelist;

int isPrime(long int number, primelist * list ,long int * calls, long int * searchcalls);
primenode * primelist_insert(long int prime, primelist * list);
int primelist_search(long int searchval, primenode * searchat, long int * calls);
void primelist_destroy(primenode * destroyat);

int main(){
    long int n;
    long int callstoisprime = 0;
    long int callstosearch = 0;
    int result = 0;
    primelist primes;

    //Initialize primelist
    primes.head = NULL;
    primes.tail = NULL;
    primes.size = 0;

    //Insert 2 as a default prime (optional step)
    primelist_insert(2, &primes);

    printf("\n\nPlease enter a number: ");
    scanf("%d",&n);
    printf("Please wait while I crunch the numbers...");
    result = isPrime(n, &primes, &callstoisprime, &callstosearch);
    switch(result){
        case 1: printf("\n%ld is a prime.",n); break;
        case -1: printf("\n%ld is a special case. It's neither prime nor composite.",n); break;
        default: printf("\n%ld is composite.",n); break;
    }
    printf("\n\n%d calls made to function: isPrime()",callstoisprime);
    printf("\n%d calls made to function: primelist_search()",callstosearch);

    //Print all prime numbers in the linked list
    printf("\n\nHere are all the prime numbers in the linked list:\n\n");
    primes.curr = primes.head;
    while(primes.curr != NULL){
        printf("%ld ", primes.curr->key);
        primes.curr = primes.curr->next;
    }
    printf("\n\nNote: Only primes up to the square root of your number are listed.\n"
                "If your number is negative, only the smallest prime will be listed.\n"
                "If your number is a prime, it will itself be listed.\n\n");

    //Free up linked list before exiting
    primelist_destroy(primes.head);

    return 0;
}

int isPrime(long int number, primelist * list ,long int * calls, long int *searchcalls){
//Returns 1 if prime
//          0 if composite
//          -1 if special case
    *calls += 1;
    long int i = 2;
    if(number==0||number==1){
        return -1;
    }
    if(number<0){
        return 0;
    }
    //Search for it in the linked list of previously found primes
    if(primelist_search(number, list->head, searchcalls) == 1){
        return 1;
    }
    //Go through all possible prime factors up to its square root
    for(i = 2; i <= sqrt(number); i++){ 
        if(isPrime(i, list,calls,searchcalls)){
            if(number%i==0) return 0; //It's not a prime
        }
    }
    primelist_insert(number, list); /*Insert into linked list so it doesn't have to keep checking
                                                if this number is prime every time*/
    return 1;
}

primenode * primelist_insert(long int prime, primelist * list){
    list->curr = malloc(sizeof(primenode));
    list->curr->next = NULL;

    if(list->head == NULL){
        list->head = list->curr;
    }
    else{
        list->tail->next = list->curr;
    }
    list->tail = list->curr;
    list->curr->key = prime;
    list->size += 1;

    return list->curr;
}

int primelist_search(long int searchval, primenode * searchat, long int * calls){
    *calls += 1;
    if(searchat == NULL) return 0;
    if(searchat->key == searchval) return 1;
    return primelist_search(searchval, searchat->next, calls);
}

void primelist_destroy(primenode * destroyat){
    if(destroyat == NULL) return;
    primelist_destroy(destroyat->next);
    free(destroyat);
    return;
}

基本上，我所见过的简单的原始性测试有很多内容：0。2是质数。1.在所有整数之间循环，从2到被测数字的一半或平方根。2.如果数字可以被任何整数整除，则中断并返回false；否则，返回false。它是复合的。3.否则，在最后一次迭代后返回true；否则，返回true。很好。

我认为您不必测试每个从2到平方根的数字，只需测试每个质数，因为所有其他数字都是质数的倍数。因此，该函数会在使用模数之前调用自身以查找数字是否为质数。这行得通，但是我认为一遍又一遍地测试所有这些素数有点乏味。因此，我使用了一个链表也存储了其中找到的每个素数，因此在测试素数之前，该程序首先搜索该清单。

是真的更快或更有效，还是我只是浪费了很多时间？我确实在计算机上对其进行了测试，但对于较大的质数，它的显示速度似乎更快，但我不确定。我也不知道它是否使用了更多的内存，因为无论我做什么，任务管理器都保持恒定的0.7 MB。

感谢您的任何答案！

Answer 1

由于您的程序仅测试一个数字，因此您在浪费时间尝试避免使用复合测试。您执行大量计算以节省一个微不足道的模运算。

如果您要连续测试多个数的素数，那么预先计算素数至该范围上限的平方根是有意义的，然后在测试候选者时对这些素数进行检验。

更好的方法是执行Eratosthenes（这里为C代码）的偏移 筛，以找到给定范围内的素数。Eratosthenes筛子从2到N找到素的时间复杂度是; 并按底数进行试验除法，直至达到sqrt （这更糟；例如，最多1百万个筛子的运行时间与100k 的运行时间之比为10.7倍，而试验除以22x； 2百万比100万的筛子运行时间为2.04倍，则为2.7倍（试用版）。O(N log log N)O(N^1.5 / (log N)^2)

Eratosthenes偏移筛的伪代码：

Input: two Integers n >= m > 1

Let k = Floor(Sqrt(n)),
Let A be an array of Boolean values, indexed by Integers 2 to k, and
    B an array of Booleans indexed by Integers from m to n,
    initially all set to True.

for i = 2, 3, 4, ..., not exceeding k:
  if A[i] is True:
    for j = i^2, i^2+i, i^2+2i, ..., not greater than k:
      A[j] := False
    for j = i^2, i^2+i, i^2+2i, ..., between m and n, inclusive:
      B[j] := False

Output: all `i`s such that B[i] is True, are all the primes 
                                     between m and n, inclusive.

常见的优化方法是仅使用赔率，i = 3,5,7,...从一开始就避免任何偶数（无论如何，已知2是质数，而任何偶数都是一个合成数）。然后，可以在两个内部循环中使用的步骤2i，而不仅仅是i。因此，偶数索引完全不包含在处理中（通常使用压缩寻址方案val = start + 2*i）。