カーマイケル数を求める

カーマイケル数を求める

#include<stdio.h>
#define NUM 10000
int i, j;

int car(int n){
	int k = n;
	if(n < 2)	return 0;
	for(i = 2; i < k; i++)
		if(!(k % i)){
			if((k / i) % i == 0)		return 0;
			if((n - 1) % (i - 1) != 0)	return 0;
			k /= i;
			i = 1;
		}
	return k != n && (n - 1) % (k - 1) == 0;
}

int main(void){
	int n;
	
	for(n = 2; n < NUM - 1; n++)
		if(car(n))
			printf("%d\n", n);
	
	return 0;
}