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<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;
}

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.

I figured that you don't have to test against every number from 2 to the square root, just every prime 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.

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.

  • 1
    Recursion never gives the fastest possible algorithm, because the function calling/return overhead takes far longer to execute than the actual comparison. Also, recursion likely forces the program to use stack where it could have used CPU registers. If you want the fastest possible algorithm, start with unrolling the recursion to a plain loop. – Lundin Oct 31 '13 at 10:48
up vote 2 down vote accepted

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.