Primality Testing–Part 1. Naïve Approaches

By roman10 On March 30, 2012 · Leave a Comment

Primality refers to determining if a given input number is prime or not. This post covers two naive approaches for primality testing.

Naive Approach 1

This most straightforward approach is to check if a given input integer n is divisible by integers from 2 to n-1. If a number is prime, then it should not divisible by any numbers in the range [2, n-1]. This is implemented as below,

/**
a naive method of determining if n is prime or not
divide from 2 to n-1
**/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int prime(int n) {
    int i;
    for (i = 2; i <= n-1; i++) {
        if (n%i == 0) {
            printf("%d is divisble by %d\n", n, i);
            return 0;
        }
    }
    return 1;
}
 
int main(int argc, char **argv) {
    int n = atoi(argv[1]);
    struct timeval stTime, edTime;
    gettimeofday(&stTime, NULL);
    if (prime(n)) {
        printf("%d is prime\n", n);
    } else {
        printf("%d is not prime\n", n);
    }
    gettimeofday(&edTime, NULL);
    printf("time: %u:%u\n", (unsigned int)(edTime.tv_sec - stTime.tv_sec), (unsigned int)(edTime.tv_usec - stTime.tv_usec));
}

Save the code to prim0.c. Compile the code with the command below,

gcc -o prim0 prim0.c –lm

Below are some sample testing results,

./prim0 2147483647
2147483647 is prime
time: 7:145569
 
./prim0 2147483640
2147483640 is divisble by 2
2147483640 is not prime
time: 0:46
 
./prim0 2
2 is prime
time: 0:51
 
./prim0 3
3 is prime
time: 0:49

Naive Approach 2: Improved Version of NA 1

The above algorithm can be improved. Firstly, if a number is divisible by an even integer, it must be divisible by 2. So we only need to check if the input number n is divisible by 2 and skip the rest of the even integers.

Secondly, if a number n is divisible by a number x, where x > sqrt(n). Then n = x*y, where y < sqrt(n), and y is also divisible by n. Therefore, we only need to check up to integer sqrt(n).

Below is the implementation with the two optimizations described,

/**
a naive method of determining if n is prime or not
divide from 2 to sqrt(n), skip the even numbers
**/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int prime(int n) {
    int i, j;
    if (n == 2) {
        return 1;
    }
    if (!(n&1)) {
        //n is even
        printf("%d is divisible by 2\n", n);
        return 0;
    }
    j = sqrt(n);
    //to be safe, run to j+1
    for (i = 3; i <= j + 1; i+=2) {
        if (n%i == 0) {
            printf("%d is divisible by %d\n", n, i);
            return 0;
        }
    }
    return 1;
}
 
int main(int argc, char **argv) {
    int n = atoi(argv[1]);
    struct timeval stTime, edTime;
    gettimeofday(&stTime, NULL);
    if (prime(n)) {
        printf("%d is prime\n", n);
    } else {
        printf("%d is not prime\n", n);
    }
    gettimeofday(&edTime, NULL);
    printf("time: %u:%u\n", (unsigned int)(edTime.tv_sec - stTime.tv_sec), (unsigned int)(edTime.tv_usec - stTime.tv_usec));
}

Note that sqrt is a floating point operation. We check until sqrt(n) + 1, just to be safe.

Save the code to prim1.c, and compile the code using the command below,

gcc -o prim1 prim1.c –lm

Below are some testing results,

roman10@ra-ubuntu-1:~/Desktop/integer/prim$ ./prim1 2
2 is prime
time: 0:50
 
roman10@ra-ubuntu-1:~/Desktop/integer/prim$ ./prim1 3
3 is prime
time: 0:60
 
roman10@ra-ubuntu-1:~/Desktop/integer/prim$ ./prim1 2147483647
2147483647 is prime
time: 0:308
 
roman10@ra-ubuntu-1:~/Desktop/integer/prim$ ./prim1 2147483641
2147483641 is divisible by 2699
2147483641 is not prime
time: 0:73