#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>
#include <string.h>

// BigInt nativo de 128 bits
typedef unsigned __int128 bigint_t;

// Tamaño del bloque: 256 KB
#define SEGMENT_SIZE_BYTES 262144
#define SEGMENT_BITS (SEGMENT_SIZE_BYTES * 8)

#define IS_COMPOSITE(arr, i)  ((arr)[(i) >> 3] &   (1U << ((i) & 7)))
#define SET_COMPOSITE(arr, i) ((arr)[(i) >> 3] |=  (1U << ((i) & 7)))

// Convertir BigInt a String decimal
void bigint_to_string(bigint_t n, char *buffer) {
    if (n == 0) { 
        buffer[0] = '0'; 
        buffer[1] = '\0'; 
        return; 
    }
    char temp[50];
    int i = 0;
    while (n > 0) {
        temp[i++] = '0' + (char)(n % 10);
        n /= 10;
    }
    int j = 0;
    while (i > 0) {
        buffer[j++] = temp[--i];
    }
    buffer[j] = '\0';
}

// Convertir BigInt a Base64 posicional (Radix-64)
void bigint_to_base64(bigint_t n, char *buffer) {
    static const char B64_ALPHABET[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    if (n == 0) {
        buffer[0] = 'A';
        buffer[1] = '\0';
        return;
    }
    char temp[50];
    int i = 0;
    while (n > 0) {
        temp[i++] = B64_ALPHABET[(int)(n % 64)];
        n /= 64;
    }
    int j = 0;
    while (i > 0) {
        buffer[j++] = temp[--i];
    }
    buffer[j] = '\0';
}

// Imprimir BigInt en decimal
void print_bigint(bigint_t n) {
    char buffer[50];
    bigint_to_string(n, buffer);
    printf("%s", buffer);
}

// Convertir BigInt a double
double bigint_to_double(bigint_t temp) {
    double n = 0.0;
    double multiplier = 1.0;
    while(temp > 0) {
        n += (double)(temp % 10) * multiplier;
        temp /= 10;
        multiplier *= 10.0;
    }
    return n;
}

// Leer BigInt desde cadena
bigint_t parse_bigint(const char *str) {
    bigint_t result = 0;
    while (*str) {
        if (*str >= '0' && *str <= '9') {
            result = result * 10 + (*str - '0');
        }
        str++;
    }
    return result;
}

// Exponenciación modular segura para 128 bits: (base^exp) % mod
bigint_t mod_pow(bigint_t base, bigint_t exp, bigint_t mod) {
    bigint_t res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// Test de primalidad Miller-Rabin optimizado para 128 bits
bool miller_rabin(bigint_t n, int k) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;

    bigint_t d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }

    static const uint64_t bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (int i = 0; i < 12; i++) {
        bigint_t a = bases[i];
        if (n <= a) break;
        bigint_t x = mod_pow(a, d, n);
        if (x == 1 || x == n - 1) continue;
        int composite = 1;
        for (int r = 1; r < s; r++) {
            x = (x * x) % n;
            if (x == n - 1) {
                composite = 0;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

// Encuentra el primer número primo mayor o igual a n
bigint_t next_prime(bigint_t n) {
    if (n <= 2) return 2;
    if (n % 2 == 0) n++;
    while (!miller_rabin(n, 5)) {
        n += 2;
    }
    return n;
}

int main(int argc, char *argv[]) {
    bigint_t target = parse_bigint("8300770764");
    if (argc >= 2) target = parse_bigint(argv[1]);

    printf("Buscando el primo numero : ");
    print_bigint(target);
    printf("\n");

    // ---------------------------------------------------------
    // FASE 1: Cálculo del techo matemático
    // ---------------------------------------------------------
    double n_double = bigint_to_double(target);
    double max_val_est = 20.0;
    
    if (n_double >= 6.0) {
        max_val_est = n_double * (log(n_double) + log(log(n_double)) + 1.0); 
    }
    
    bigint_t limit_sqrt = (bigint_t)sqrt(max_val_est) + 100000;

    // ---------------------------------------------------------
    // FASE 2: Generar Primos Base
    // ---------------------------------------------------------
    size_t base_mem_size = (size_t)(limit_sqrt / 8) + 1;
    unsigned char *base_sieve = (unsigned char *)calloc(base_mem_size, 1);
    
    if(!base_sieve) {
        printf("Error: No se pudo asignar memoria base.\n");
        return 1;
    }

    for (bigint_t p = 2; p * p <= limit_sqrt; p++) {
        if (!IS_COMPOSITE(base_sieve, p)) {
            for (bigint_t i = p * p; i <= limit_sqrt; i += p) {
                SET_COMPOSITE(base_sieve, i);
            }
        }
    }

    size_t base_primes_count = 0;
    for (bigint_t p = 2; p <= limit_sqrt; p++) {
        if (!IS_COMPOSITE(base_sieve, p)) base_primes_count++;
    }
    
    bigint_t *primes = (bigint_t *)malloc(base_primes_count * sizeof(bigint_t));
    size_t idx = 0;
    for (bigint_t p = 2; p <= limit_sqrt; p++) {
        if (!IS_COMPOSITE(base_sieve, p)) primes[idx++] = p;
    }
    free(base_sieve);

    // ---------------------------------------------------------
    // FASE 3: LA CRIBA SEGMENTADA
    // ---------------------------------------------------------
    printf("\nIniciando busqueda profunda...\n");
    unsigned char *segment = (unsigned char *)malloc(SEGMENT_SIZE_BYTES);
    
    bigint_t count = 0;
    bigint_t low = 2;
    bigint_t nth_prime = 0;
    bigint_t latest_prime_found = 0; 
    
    clock_t start_cpu_time = clock();
    time_t wall_start_time = time(NULL);
    
    clock_t last_print_time = start_cpu_time;
    double target_double = bigint_to_double(target);

    while (count < target) {
        for(size_t i = 0; i < SEGMENT_SIZE_BYTES; i++) segment[i] = 0;
        
        bigint_t high = low + SEGMENT_BITS - 1;

        if (high > limit_sqrt * limit_sqrt) {
            printf("\n[Error Matematico] Se requiere ampliar la estimacion base.\n");
            break;
        }

        for (size_t i = 0; i < base_primes_count; i++) {
            bigint_t p = primes[i];
            if (p * p > high) break;

            bigint_t first_multiple = (low / p) * p;
            if (first_multiple < low) first_multiple += p;
            if (first_multiple == p)  first_multiple += p;

            for (bigint_t j = first_multiple; j <= high; j += p) {
                SET_COMPOSITE(segment, (size_t)(j - low));
            }
        }

        for (size_t i = 0; i < SEGMENT_BITS; i++) {
            if (!IS_COMPOSITE(segment, i)) {
                count++;
                latest_prime_found = low + i; 
                if (count == target) {
                    nth_prime = latest_prime_found;
                    break;
                }
            }
        }
        
        // ---------------------------------------------------------
        // ACTUALIZACIÓN DE PROGRESO (\r)
        // ---------------------------------------------------------
        clock_t current_cpu_time = clock();
        if ((double)(current_cpu_time - last_print_time) / CLOCKS_PER_SEC >= 0.25) {
            double current_double = bigint_to_double(count);
            double percentage = (current_double / target_double) * 100.0;
            
            // --- CÁLCULO DE LA PROPORCIÓN (RATIO) ---
            char ratio_buf[20] = "  1 / 1.0000";
            if (percentage > 0 && percentage < 100.0) {
                if (percentage < 50.0) {
                    double val = 100.0 / percentage;
                    snprintf(ratio_buf, sizeof(ratio_buf), "  1 / %6.4f", val);
                } else {
                    double val = percentage / (100.0 - percentage);
                    snprintf(ratio_buf, sizeof(ratio_buf), "%6.4f / 1  ", val);
                }
            }

            // --- CÁLCULO DEL PRIMO ESTIMADO REAL Y BASE64 ---
            bigint_t estimated_prime = latest_prime_found;
            time_t now_wall_time = time(NULL);
            double elapsed_wall_sec = difftime(now_wall_time, wall_start_time);
            
            if (current_double > 1000.0) {
                double pnt_target = target_double * log(target_double);
                double pnt_current = current_double * log(current_double);
                double est_val = bigint_to_double(latest_prime_found) * (pnt_target / pnt_current);
                estimated_prime = next_prime((bigint_t)est_val);
            }

            // Conversión del número a String y Base64 posicional
            char est_str[50];
            char est_b64[50];
            bigint_to_string(estimated_prime, est_str);
            bigint_to_base64(estimated_prime, est_b64);

            // --- CÁLCULO ETA ---
            char eta_buf[30] = "Calculando...";
            if (elapsed_wall_sec >= 2.0 && current_double > 0) {
                double rate = current_double / elapsed_wall_sec;
                double remaining_sec = (target_double - current_double) / rate;
                
                time_t eta_time = now_wall_time + (time_t)remaining_sec;
                struct tm *eta_tm = localtime(&eta_time);
                if (eta_tm != NULL) {
                    strftime(eta_buf, sizeof(eta_buf), "%Y-%m-%d %H:%M:%S", eta_tm);
                }
            }

            // Impresión con el formato deseado
            printf("\r[%6.2f%% | %s] P: ", percentage, ratio_buf);
            print_bigint(latest_prime_found);
            printf(" | Est: %s %s | ETA: %s   ", est_str, est_b64, eta_buf);
            fflush(stdout);
            
            last_print_time = current_cpu_time;
        }

        if (nth_prime > 0) break;
        low += SEGMENT_BITS;
    }

    // Limpieza final de la línea
    printf("\r                                                                                                                                                                                              \r");
    
    double elapsed_total = (double)(clock() - start_cpu_time) / CLOCKS_PER_SEC;

    // ---------------------------------------------------------
    // RESULTADOS
    // ---------------------------------------------------------
    printf("\n================ RESULTADOS ================\n");
    printf("El primo numero ");
    print_bigint(target);
    printf(" es : ");
    print_bigint(nth_prime);
    printf("\n");
    
    char final_b64[50];
    bigint_to_base64(nth_prime, final_b64);
    
    printf("En formato Base64     : %s\n", final_b64);
    printf("Tiempo de calculo     : %.2f segundos\n", elapsed_total);
    printf("Memoria RAM total     : < 5 MB\n");
    printf("============================================\n");

    free(primes);
    free(segment);
    return 0;
}