数値が素数かどうかをテストするこのプログラムを 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 を返します。それは合成です。3. それ以外の場合は、最後の繰り返しの後に true を返します。プライムです。
他のすべての数値は素数の倍数であるため、2 から平方根までのすべての数値に対してテストする必要はなく、すべての素数に対してテストする必要があると考えました。そのため、関数は自分自身を呼び出して、モジュラスを使用する前に数値が素数かどうかを調べます。これは機能しますが、これらすべての素数を何度も何度もテストし続けるのは少し面倒だと思いました。そこで、リンク リストを使用して、その中に見つかったすべての素数を格納し、素数性をテストする前に、プログラムが最初にリストを検索するようにしました。
それは本当に速いですか、それともより効率的ですか、それとも単に多くの時間を無駄にしただけですか? 私は自分のコンピューターでテストしましたが、素数が大きいほど高速に見えましたが、よくわかりません. また、タスク マネージャーは何をしても一定の 0.7 MB のままであるため、大幅に多くのメモリを使用するかどうかもわかりません。
回答ありがとうございます。