Rabin Miller Primality test

Meh
// Find a witness for the Rabin-Miller test
// http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
// (variable names following article)

#include <stdio.h>
#include <math.h>

int gcd(int a, int b) {
int c;
while(a != 0) {
c = a;
a = b%a;
b = c;
}
return b;
}

int maxpowerof2(int n) {
int r = 0;
while(n % 2 == 0) {
n /= 2;
r++;
}
return r;
}

int main(void) {
int r, n, a, i, s, d;
printf("Give n: ");
fflush(stdout);
scanf("%d", &n);
s = maxpowerof2(n - 1);
d = (n - 1)/pow(2, s);
printf("n - 1 = 2^s * d\n"
"%d = 2^(%d) * %d\n", n - 1, s, d);
for(a = 1; a < n; a++) {
if(gcd(a, n) == 1) {
if((int)pow(a, d) % n != 1) {
for(r = 0; r < s; r++)
if((int)pow(a, pow(2, r)*d) % n == n - 1) break;
if(r == s) {
printf("Found a witness: %d\n", a);
break;
}
}
}
}
return 0;
}

>>34

Because it's not a bool.

It makes no difference (not if you're using _Bool, anyway, and not some other disgusting pre-C99 hack).

May people's motivation for this is the fact that

while (!a)

is really easy to mistake for

while (a)

if you've been staring at your display too long and are slowly going blind. The following are also popular with the Perl crowd, for the same reason:

#define until(a) while (!(a))
#define unless(a) if ((!a))