如果一个数是素数，递归迭代法比纯迭代法好吗？

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 到 1 半的所有整数或被测数字的平方根。2. 如果数字可以被任何东西整除，则打破并返回false;它是复合的。3. 否则，在上次迭代后返回 true;它是黄金时期。

我认为你不必测试从2到平方根的每个数字，只需要测试每个素数，因为所有其他数字都是素数的倍数。因此，该函数调用自己以在使用模数之前找出一个数字是否是素数。这很有效，但我认为一遍又一遍地测试所有这些素数有点乏味。因此，我使用链表来存储其中找到的每个素数，以便在测试primarty之前，程序首先搜索列表。

它真的更快、更高效吗？还是我浪费了很多时间？我确实在我的电脑上测试了它，对于较大的素数，它似乎更快，但我不确定。我也不知道它是否会使用更多的内存，因为无论我做什么，TaskManager都会保持0.7MB不变。

谢谢你的回答！

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

不要循环遍历所有数字，只需循环遍历链接列表中的数字：

// Go through all possible prime factors up to its square root
primenode *p;
for (p = primes.head; p->key <= sqrt(number); p = p->next) { 
        if (number%(p->key) == 0) return 0; //It's not a prime
    }
}

Answer 2

由于您的程序只测试一个数字，您试图避免通过复合测试是在浪费时间。您执行大量计算来节省一个微不足道的模运算。

如果您在一行中测试多个数字的素数，那么将素数预先计算到该范围上限的平方英尺，并在测试候选者时遍历这些素数是有意义的。

更好的是对埃拉托色尼进行偏移筛分（此处为C代码），以找到给定范围内的质数。埃拉托色尼筛分查找从2到N的质数的时间复杂度为O（N log log N）；按质数进行审判分割直到sqrt，O（N^1.5/（log N）^2）（这更糟糕；例如，与100k相比，筛分100万的运行时间比为10.7倍，vs 22倍；200万vs100万是筛分的2.04倍，审判分割的2.7倍）。

埃拉托斯特尼偏移筛伪码：

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）。