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`

References:
1. Wikipedia Primality Test: http://en.wikipedia.org/wiki/Primality_test
2. Algorithms by Dasgupta, CH Papadimitriou and UV Vazirani