17.c

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

#define N 100000
#define N_ITER 10
#define long_int unsigned long long int

long_int randf(long_int a){
	return (rand()%(a-2))+2;
}

long_int power(long_int base, long_int exp){
	long_int r = 1;
	while(exp--)
		r*=base;

	return r;
}

long_int powmod(long_int base, long_int exp, long_int mod){
	if(exp > 1){
		long_int f = powmod(base, exp/2, mod);
		if(exp%2)
			return (f*f*(base%mod))%mod;
		return (f*f)%mod;
	}
	return base%mod;
}

int naive(long_int n){
	int d = 3;

	float square_root = sqrt(n);

	if(!(square_root - ((int)square_root)) || !(n%2)){
		return (n==2)?1:0;
	}

	while(n%d){
		d+=2;
		if(d > square_root)
			return 1;
	}

	return (n==3)?1:0;
}

int fermat(long_int n, long_int iter){
	if(!(n%2))
		return (n==2)?1:0;

	long_int i;
	for(i=0 ; i<iter; i++){
		long_int a = randf(n);
		if(powmod(a, n-1, n) != 1)
			return 0;
	}

	return 1;
}

int miller(long_int n){

}

int main(){
	srand(time(0));
	int i;
	int n_naive=0;
	int n_fermat=0;

	for(i=0; i<N; i++){
		int n = naive(i);
		int f = fermat(i, N_ITER);
		if(n) n_naive++;
		if(f) n_fermat++;

		if(n!=f)
			printf("%d\tn:%s\tf:%s\n", i, n?"PRIMO":"COMPOSTO", f?"PRIMO":"COMPOSTO");

	}
	printf("n:%d/f:%d\n", n_naive, n_fermat);
	return 0;
}