我用 C 语言编写了这个程序来测试一个数字是否是素数。我还不熟悉算法复杂性和所有大 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.如果数能被任何东西整除，则break并返回false；它是复合的。3.否则，最后一次迭代后返回true；这是主要的。
我认为您不必针对从 2 到平方根的每个数字进行测试，只需针对每个素数进行测试，因为所有其他数字都是素数的倍数。因此，该函数调用自身来确定一个数字是否为素数，然后再对其使用模数。这行得通，但我认为一遍又一遍地测试所有这些素数有点乏味。因此，我也使用了一个链表来存储在其中找到的每个素数，以便在测试素数之前，程序首先搜索列表。
它真的更快，或更高效，还是我只是浪费了很多时间？我确实在我的电脑上对其进行了测试，对于较大的素数，它确实看起来更快，但我不确定。我也不知道它是否使用了更多的内存，因为无论我做什么，任务管理器都保持恒定的 0.7 MB。
感谢您的任何回答！