Fundamentos Matemáticos:

Números Primos: Un número natural mayor que 1 que solo es divisible por 1 y por sí mismo se denomina número primo. Los números que no cumplen esta propiedad se llaman compuestos (el 1 no se considera ni primo ni compuesto).

Factores Primos: Son los números primos que dividen exactamente a un entero positivo dado.

Máximo Común Divisor (MCD): El mayor divisor común entre dos o más enteros positivos.

Propiedad Fundamental: Excepto el 1, el divisor más pequeño de cualquier número siempre es un número primo.

Problema 1: Verificcaión de Primos mediante División Experimental

Se proporcionan n enteros positivos ai. Determinar si cada número es primo.

Entrada: Primera línea con n, seguida de n líneas con los valores ai.

Salida: n líneas indicando "Yes" si es primo, "No" en caso contrario.

Restricciones: 1 ≤ n ≤ 100, 1 ≤ ai ≤ 2^31 − 1

Implementación:

#include <iostream>
#include <cmath>

bool verificarPrimo(int valor)
{
    if (valor < 2) return false;
    int limite = static_cast<int>(sqrt(valor));
    for (int divisor = 2; divisor <= limite; divisor++)
    {
        if (valor % divisor == 0)
            return false;
    }
    return true;
}

int main()
{
    int cantidad;
    std::cin >> cantidad;
    
    for (int i = 0; i < cantidad; i++)
    {
        int numero;
        std::cin >> numero;
        std::cout << (verificarPrimo(numero) ? "Yes" : "No") << std::endl;
    }
    return 0;
}

Problema 2: Descomposición en Factores Primos

Para n enteros positivos dados, descomponer cada uno en sus factores primos. Mostrar cada factor junto con su exponente.

Entrada: Primera línea con n, seguida de n líneas con los valores ai.

Salida: Para cada número, mostrar factor y exponente en líneas separadas. Dejar una línea en blanco después de cada caso.

Restricciones: 1 ≤ n ≤ 100, 2 ≤ ai ≤ 2×10^9

Implementación:

#include <iostream>

void descomponer(int numero)
{
    for (int factor = 2; factor <= numero / factor; factor++)
    {
        if (numero % factor == 0)
        {
            int exponente = 0;
            while (numero % factor == 0)
            {
                numero /= factor;
                exponente++;
            }
            std::cout << factor << " " << exponente << std::endl;
        }
    }
    if (numero > 1)
        std::cout << numero << " 1" << std::endl;
    std::cout << std::endl;
}

int main()
{
    int cantidad;
    std::cin >> cantidad;
    
    while (cantidad--)
    {
        int numero;
        std::cin >> numero;
        descomponer(numero);
    }
    return 0;
}

Problema 3: Criba para Ancontrar Números Primos

Dado un número n, determinar cuántos primos existen entre 1 y n.

Entrada: Un solo entero n.

Salida: Un entero con la cantidad de primos en el rango [1, n].

Restricciones: 1 ≤ n ≤ 10^6

Implementación - Método Básico O(nlogn):

#include <iostream>

const int MAXIMO = 1000010;

int listaPrimos[MAXIMO];
int contador = 0;
bool marcado[MAXIMO];

void generarPrimos(int limite)
{
    for (int i = 2; i <= limite; i++)
    {
        if (!marcado[i])
            listaPrimos[contador++] = i;
        
        for (int j = i + i; j <= limite; j += i)
            marcado[j] = true;
    }
}

int main()
{
    int n;
    std::cin >> n;
    generarPrimos(n);
    std::cout << contador << std::endl;
    return 0;
}

Método de Eratóstenes O(nloglogn):

void generarPrimos(int limite)
{
    for (int i = 2; i <= limite; i++)
    {
        if (!marcado[i])
        {
            listaPrimos[contador++] = i;
            for (int j = i + i; j <= limite; j += i)
                marcado[j] = true;
        }
    }
}

Criba Lineal O(n):

void generarPrimos(int limite)
{
    for (int i = 2; i <= limite; i++)
    {
        if (!marcado[i])
            listaPrimos[contador++] = i;
        
        for (int j = 0; listaPrimos[j] <= limite / i; j++)
        {
            marcado[listaPrimos[j] * i] = true;
            if (i % listaPrimos[j] == 0)
                break;
        }
    }
}

Problema 4: Cálculo del Máximo Común Divisor

Dados n pares de enteros positivos (ai, bi), determinar el MCD de cada par.

Entrada: Primera línea con n, seguida de n líneas con pares ai bi.

Salida: n líneas con el MCD de cada par.

Restricciones: 1 ≤ n ≤ 10^5, 1 ≤ ai, bi ≤ 2×10^9

Implementación con Algoritmo de Euclides:

#include <iostream>

int calcularMCD(int a, int b)
{
    return (b == 0) ? a : calcularMCD(b, a % b);
}

int main()
{
    int cantidad;
    std::cin >> cantidad;
    
    while (cantidad--)
    {
        int a, b;
        std::cin >> a >> b;
        std::cout << calcularMCD(a, b) << std::endl;
    }
    return 0;
}

Versión Alternativa usando STL:

#include
#include

int main()
{
int cantidad;
std::cin >> cantidad;

while (cantidad--)
{
int a, b;
std::cin >> a >> b;
std::cout << std::gcd(a, b) << std::endl;
}
return 0;
}