Is a Recursive-Iterative Method Better than a Purely Iterative Method to find out if a number is prime?

I made this program in C that tests if a number is prime. I'm as yet unfamiliar with Algorithm complexity and all that Big O stuff, so I'm unsure if my approach, which is a combination of iteration and recursion, is actually more efficient than using a purely iterative method.

```
#include
#include
#include

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

So after looking at this we can do some basic BigO analysis(recursion aside)

so we have your number linked list(O(n)) + prime function(O(sqrt(n)) so lets just go with O(n) since it is larger so really yes this way is slower for smaller numbers since primes tend to be closer together when numbers are small.

You are also using memory to store that linked list which does grow as the number of primes grow. I'm not sure the added complexity is really worth the possible benefits you are receiving here for larger numbers(although I'm not quite sure where the tipping point begins to tip in your favor) maybe when you reached n > sqrt(number of primes below n?)

If you are really looking for possible speed boosts maybe use something like a dictionary to store your prime numbers O(1) or really anything that has a better look up than O(n) but again you'll be using memory as a consequence.

StackExchange Code Review Q#33397, answer score: 2