Tuesday, October 12, 2010

To test Prime Number

#include <stdio.h>


typedef enum {
    FALSE = 0,
    TRUE = 1
} BOOL;

char *boolstr[] = {"FALSE", "TRUE"};

BOOL is_even(unsigned int k)
{
    if (k % 2) return FALSE;
    return TRUE;
}

BOOL is_prime(unsigned long k, unsigned long *divisor)
{
    unsigned long testnum,testlimit;
    BOOL ret = FALSE;

    if (k == 1) return FALSE; // 1 is neigher prime neither composite
    if (k == 2) return TRUE;
    if (is_even(k)) return FALSE; // even numbers are never prime, except 2
    testlimit = k;
    testnum = 3;
    while (testnum < testlimit) {
        //printf("highest prime divisor=%lu\n",*divisor);
        if ( (k % testnum) == 0)
        {
            *divisor = testnum;
            printf("div=%lu\n", *divisor);
            return FALSE; //return TRUE;
            // k is not prime as it is divisable by l

        }
        testlimit = k/testnum;
        testnum += 2;

    }
    return TRUE;
}


int main()
{
    unsigned long k,divisor;

    divisor=1;
    printf("Enter an integer: ");
    scanf("%lu", &k);
    printf("k=%lu is even? %s\n", k, boolstr[is_even(k)]);
    if (is_prime(k, &divisor))
    {
        printf("k=%lu is prime? %s\n", k, boolstr[TRUE]);
    }
    else
    {
        printf("%lu is NOT prime\n", k);
        //printf("highest prime divisor = %lu\n", divisor);
    }
}

1 comment:

  1. Lutfi,

    You can make it faster by dividing the number with the previous prime numbers, up to the square root of that number.



    KOkon.

    ReplyDelete