/* NaN -- console "fast" Prime Number Test/Generator
 * Copyright (C) 2013 Gustavo Loureiro Conte (gustavo at ventania.blog.br)
 * $Id: nan.c,v 1.29 2013/12/07 17:30:03 Guzpido Krush $
	http://www.sansakroma.com.br/wp/ -> Fr33 POETRY and updates for this software.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

// TO COMPILE THIS SOFTWARE INSTALL libgmp 
// Ubuntu: apt-get install libgmp3-dev
// then compile as follow: $ gcc nan.c -o NaN -lgmp -lm
// to run the program, type ./NaN
// Program accepts a number as parameter,
// it tests for primality and silently exits if it is not a prime,
// while it prints the number if the number is prime. This behavior is useful for scripts.
// In normal mode of operation, program will test for primes from itt_begin to itt_max; see comments below.

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

void main (int argc, char *argv[]) {

	int binan=0; // seta operação em Binário (1) ou Decimal (0)

	// teste pseudoprimos
	int prime_flag=1;
	mpz_t itt_minus, itt_mod;
	mpz_t seis, c, ps_mod, dois, fermat;	// Para testar o Pequeno Teorema de Fermat ou se são pares
	long long int itt_len=0;
	char itt_str[1000000]; // ajustar em função das casas de max_itt (lembre-se do modo BINÁRIO)
	char buf[2]; // buffer para guardar 1 char + NULL

	// Controle do programa
	int j=0;
        mpz_t itt, max_itt, itt_begin;

	// init pseudoprimos
	mpz_init(ps_mod); mpz_init(dois); mpz_init(fermat);
	mpz_init(itt_mod); mpz_init(c); mpz_init(seis);
        mpz_set_str(dois, "2", 10);
        mpz_set_str(seis, "6", 10);
	itt_str[0] = '\0';
	buf[1] = '\0';

	// init controle do prog
        mpz_init(itt); mpz_init(max_itt); mpz_init(itt_begin);
        mpz_set_str(max_itt, "1000000000000", 10); // aqui se seta max_itt -- o programa não roda infinitamente
        mpz_set_str(itt_begin, "1", 10); // aqui se seta quando o algoritmo começa a rodar 
	// default: 1 ultimo da lista online: 9999999943
	

	if ( argc >1 ) {
		mpz_set_str(itt_begin, argv[1], 10);
		mpz_add_ui(itt_begin, itt_begin, 1);
		mpz_set(max_itt, itt_begin);
		mpz_sub_ui(itt_begin, itt_begin, 2);
		if( mpz_cmp_ui(itt_begin, 1) != 1 ) printf("2\n");
	} else 	if( mpz_cmp_ui(itt, 2) != 1 ) printf("2\n");

	mpz_set(itt, itt_begin);
	
        while ( mpz_cmp (itt, max_itt) != 0 ) {
		
		mpz_add_ui(itt, itt, 1); // incremento de 1 em 1 :( bye bye Fibonacci;
		
		if ( argc > 1 ) { j++; if ( j > 1 ) break; }
		
		// elimina numeros pares da jogada 
		mpz_mod_ui(ps_mod, itt, 2);
		if ( mpz_cmp_ui(ps_mod, 0) == 0 && mpz_cmp_ui(itt, 2) != 0 ) continue;
		// isso é feito para agilizar
		// não executando todo o algoritmo em números que de cara não são primos!
				// Aplica Teste de Fermat //		
        				mpz_set(c, itt);
        				mpz_sub_ui(c, c, 1); 
					mpz_powm (fermat, dois, c, itt); // 2^n-1 mod n

                		        if ( mpz_cmp_si(fermat, 1) == 0 )  { // se o resultado é 1, PASSOU NO TESTE DE FERMAT
					        mpz_get_str (itt_str, 10, itt); 
								// MODO BRUTE-FORCE (lento) //
								prime_flag=1;
							itt_len = strlen(itt_str);
							if ( itt_len > 2 ) 
								if ( itt_len < 6 ) { // Números menores que 6 casas.( i.e: 99999 )
									itt_len = pow(2, itt_len-2)+1;   // <- desde este número
                                                                        mpz_set_ui(c, itt_len);
                                                                        itt_len = strlen(itt_str);
                                                                        mpz_div_ui(ps_mod, itt, pow(5, itt_len-2)); // <- dividirá até este número
								}
								else { // Números maiores ou com 6 casas............( i.e 999999 )
									mpz_set_ui(itt_mod, itt_len);
									mpz_sub_ui(itt_mod, itt_mod, 6);
									mpz_powm (c, dois, itt_mod, itt); //  c = 2^itt_len-6 mod itt
									mpz_add_ui(c, c, 1);
									itt_len = strlen(itt_str);
									mpz_set_ui(itt_mod, itt_len);
                                                                        mpz_sub_ui(itt_mod, itt_mod, 5);
                                                                        mpz_powm (ps_mod, seis, itt_mod, itt); //  6^itt_len-5 mod itt
                                                                        mpz_div (ps_mod, itt, ps_mod); //  6^itt_len-5 mod itt
								}					

							while ( mpz_cmp (ps_mod, c) == 1 ) {
                	                		// TESTA dividindo 
								if ( mpz_cmp(itt, c) != 0 ) // cuidado para não dividir pelo próprio número!
									mpz_mod(itt_mod, itt, c);
						                        if ( mpz_cmp_ui(itt_mod, 0) == 0 ) { prime_flag = 0; break; } // ok, não é primo.
									mpz_add_ui(c, c, 1);
							}
							
							if ( prime_flag == 0 ) continue;

						if ( binan == 1 ) {
							mpz_get_str(itt_str, 2, itt);
							printf("%s\n", itt_str); // CONFIRMADO PRIMO!
						}
						else { 
							gmp_printf("%Zd\n", itt); //  CONFIRMADO PRIMO!
						}
					}
					else
						continue; // Não passou no Teste de Fermat
	} // loop principal
//////////
} // fim. by Gustavo Loureiro Conte dez/2013