this code is a more efficient simple C primality check than the other one that is readily findable on the internet. notes at the bottom.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main (void)
{
int x;
//get input x
printf(“Enter integer: “);
scanf (“%d”, &x);
printf(“%d”, x); //output the number to reduce redundancy later.
//2 is prime.
if (x == 2)
{
printf (” is prime\n”);
return 0;
}
//if x less than 2 OR even OR divisible by 3, it’s not prime.
if (x < 2 || x % 2 == 0 || x % 3 == 0)
{
printf (” is not prime.\n”);
return 0;
}
//passed our initial testing? time for the loop.
int i, c, l;
l = sqrt(x) + 1; //a composite has at least two factors, one of which must be < or = sqrt(composite). so we don’t need to test candidates > sqrt(x).
for (i = 1, c = 0; ((6*i)-1) < l; i++, c++)
{
if (x%((6*i)+1) == 0 || x%((6*i)-1) == 0)
{
printf(” is not prime, %d iterations.\n”, c);
return 0;
}
}
//if loop ends, x is prime.
printf( ” is prime, %d iterations.\n”, c);
return 0;
}
MATHEMATICAL BASIS JAMZ:
so fun fact: you can make any integer with the form 6k + i where i = {-1, 0, 1, 2, 3, 4}.
now, notice how this code first rules out any even input. that rules out all integers that could be formed by 6k + i where i = {0, 2, 4}.
it also rules out any input divisible by 3. that rules out all integers of the form 6k + i where i = {3}.
that leaves us with integers of the form 6k +/- 1. in fact, all prime numbers are of the form 6k +/- 1 (that is, primes are a perfect subset of the set of numbers formed by 6k +/- 1). in reality, you only need to check if an (odd) input is divisible by the primes between 2 and sqrt(input), but this method is quick, dirty and 3 times more efficient than iterating through all odd numbers.
