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

int cuentaBits(int numero) {
      int bits_necesarios = 0;
      while(numero > 0) {
            bits_necesarios++;
            numero = numero >> 1 ; // Desplazo bits (división por 2)
      }
      return bits_necesarios;
}
int* binario( int n , int array [],int size){
	
	for (int i = size-1; i > -1 ; i--){
		array[i] = n%2;
		n = n / 2;
	}
	return  array;
}


int expModular(int b, int n,int m){
	//Funcion para el calculo de la exponenciacion modular 
	// Se obtiene (b^n)%m muy funcional si son enteros grandes
	int k = cuentaBits(n);
	int temp[k];

	int* rep = binario(n,temp,k);
	
 	int x = 1;
	int potencia = b % m;
	for(int i = k-1; i > -1; i--){
		if (rep[i]){
			x = (x * potencia) % m;
		}
		potencia = (potencia * potencia) % m;
	}
	return x;
}

int millerTest(int d, int n){ 
    /*---------------Falta entender----------*/
    // Numero aleatorio entre [2..n-2] 
    
    // Corner cases make sure that n > 4 
    int a = 2 + rand() % (n - 4); 
  
    // Calcular a^d % n 
    int x = expModular(a,d,n);
    
    if (x == 1  || x == n-1) 
       return 1; 
  
    // Keep squaring x while one of the following doesn't 
    // happen 
    // (i)   d does not reach n-1 
    // (ii)  (x^2) % n is not 1 
    // (iii) (x^2) % n is not n-1 
    while (d != n-1) 
    { 
        x = (x * x) % n; 
        d = d * 2; 
  
        if (x == 1)      return 0; 
        if (x == n-1)    return 1; 
    } 
  
    return 0; /*Compuesto*/
} 
int isPrime(int n, int iterations){
	
	/*Casos < 3*/
	if(n == 2 || n == 3){
		return 1;
	}
	if(n < 4  || n%2 == 0){ /*Revisar pares y negativos y 1 */
		return 0;
	}
	int d = n - 1;
	while(d%2 == 0){ /*Mientras es par*/
		d = d/2;  
	}
	
	for (int i = 0; i < iterations; i++){
         if (!millerTest(d, n)) {
              return 0; 
         }
	}
	return 1;
}

int main(void) {
	int i = 0;
	int n = 0;

	int k = 100; /*Nivel de precicion*/  
  
    for (int n = 1; n < 100; n++) {
       if (isPrime(n, k)) {
          printf(" %i ", n);
       }
    }
    return 0; 

}