我用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. 如果数字可被任何东西整除，则中断并返回false; 它是复合物。 3. 否则，在最后一次迭代后返回true; 它是素数。
我认为您不必针对2到平方根的每个数字进行测试，只需要针对每个质数进行测试，因为所有其他数字都是质数的倍数。因此，在使用模运算之前，函数会调用自身以查找数字是否为质数。这样可以工作，但我认为反复测试所有这些质数有点繁琐。 因此，我使用了一个链接列表来存储其中发现的每个素数，以便在测试素性之前程序首先搜索该列表。
它真的更快，更高效，还是我浪费了很多时间？我在计算机上对其进行了测试，对于较大的质数似乎确实更快，但我不确定。我也不知道它是否使用了显着更多的内存，因为任务管理器无论我做什么都保持恒定的0.7 MB。
感谢任何答案！