title: Is a Recursive-Iterative Method Better than a Purely Iterative Method to find out if a number is prime?
body: <p>I made this program in C that tests if a <strong>number is prime</strong>. I'm as yet unfamiliar with Algorithm complexity and all that Big O stuff, so I'm unsure if my approach, which is a <strong>combination of iteration and recursion</strong>, is actually more efficient than using a <strong>purely iterative</strong> method.</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  #include&lt;math.h&gt;
  
  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, &amp;primes);
  
      printf("\n\nPlease enter a number: ");
      scanf("%d",&amp;n);
      printf("Please wait while I crunch the numbers...");
      result = isPrime(n, &amp;primes, &amp;callstoisprime, &amp;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-&gt;key);
          primes.curr = primes.curr-&gt;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&lt;0){
          return 0;
      }
      //Search for it in the linked list of previously found primes
      if(primelist_search(number, list-&gt;head, searchcalls) == 1){
          return 1;
      }
      //Go through all possible prime factors up to its square root
      for(i = 2; i &lt;= 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-&gt;curr = malloc(sizeof(primenode));
      list-&gt;curr-&gt;next = NULL;
  
      if(list-&gt;head == NULL){
          list-&gt;head = list-&gt;curr;
      }
      else{
          list-&gt;tail-&gt;next = list-&gt;curr;
      }
      list-&gt;tail = list-&gt;curr;
      list-&gt;curr-&gt;key = prime;
      list-&gt;size += 1;
  
      return list-&gt;curr;
  }
  
  int primelist_search(long int searchval, primenode * searchat, long int * calls){
      *calls += 1;
      if(searchat == NULL) return 0;
      if(searchat-&gt;key == searchval) return 1;
      return primelist_search(searchval, searchat-&gt;next, calls);
  }
  
  void primelist_destroy(primenode * destroyat){
      if(destroyat == NULL) return;
      primelist_destroy(destroyat-&gt;next);
      free(destroyat);
      return;
  }
  </code></pre>
  
  <p>Basically, a lot of what I've seen simple primalty tests do is:
  0. 2 is a prime.
  1. Cycle through all integers from 2 to half or the square root of the number being tested.
  2. If the number is divisible by anything, break and return false; it's composite.
  3. Otherwise, return true after the last iteration; it's prime.</p>
  
  <p>I figured that you don't have to test against every number from 2 to the square root, just every <em>prime</em> number, because all other numbers are multiples of primes. So, the function calls itself to find out if a number is prime before using the modulus on it. This works, but I thought it a bit tedious to keep testing all those primes over and over again.
  So, I used a linked list to store every prime found in it as well, so that before testing primalty, the program searches the list first.</p>
  
  <p>Is it really faster, or more efficient, or did I just waste a lot of time? I did test it on my computer, and for the larger primes it did seem faster, but I'm not sure. I also don't know if it uses significantly more memory since Task Manager just stays a constant 0.7 MB whatever I do.</p>
  
  <p>Thanks for any answers!</p>