O projeto ACM-ICPC-Preparasion visa auxiliar entusiastas de competições de algoritmos com implementações de algoritmos clássicos. Este artigo explora a lógica fundamental por trás do Crivo de Eratóstenes e do Algoritmo de Euclides, destacando seus princípios essenciais e métodos eficiantes de implementação.

Crivos de Primos: Da Teoria à Eficiência

Os métodos de crivo de primos são essenciais em teoria dos números para identiifcar rapidamente todos os números primos dentro de um determinado intervalo. Em competições como a ACM-ICPC, algoritmos eficientes de geração de primos são cruciais para resolver uma variedade de problemas.

A Essência do Crivo de Eratóstenes

O Crivo de Eratóstenes funciona marcando os múltiplos de números primos como não primos, identificando assim os primos. O algoritmo começa com o número 2 e itera, marcando progressivamente os múltiplos de cada número primo encontrado.

Uma implementação em Python encontrada no projeto demonstra essa abordagem. Ela utiliza um array booleano para rastrear o status de primalidade. Para cada número primo descoberto, seus múltiplos são marcados como compostos:

def crivo_eratostenes_otimizado(limite):
   # Inicializa todos os números como potencialmente primos
   eh_primo = [True] * (limite + 1)
   eh_primo[0] = eh_primo[1] = False  # 0 e 1 não são primos
   primos_encontrados = []

   # Itera apenas até a raiz quadrada do limite
   for numero in range(2, int(limite**0.5) + 1):
       if eh_primo[numero]:
           primos_encontrados.append(numero)
           # Começa a marcar múltiplos a partir do quadrado do número atual
           for multiplo in range(numero * numero, limite + 1, numero):
               eh_primo[multiplo] = False

   # Adiciona os primos restantes maiores que a raiz quadrada
   for numero in range(int(limite**0.5) + 1, limite + 1):
       if eh_primo[numero]:
           primos_encontrados.append(numero)

   return primos_encontrados
 

Otimizações Chave

Esta implementação incorpora duas otimizações principais:

1. A iteração vai apenas até a raiz quadrada do limite (√n). Isso ocorre porque qualquer número composto maior que √n deve ter um fator primo menor que √n.
2. A marcação dos múltiplos começa a partir do quadrado do número atual (i²). Múltiplos menores já teriam sido marcados por primos anteriores.

Essas otimizações resultam em uma complexidade de tempo de O(n log log n), tornando-o um método preferido para gerar primos em larga escala.

Algoritmo de Euclides: Cálculo Eficaz de MDC

O Algoritmo de Euclides, também conhecido como método de divisão sucessiva, é um método clássico para encontrar o máximo divisor comum (MDC) de dois números. Ele se baseia no princípio de que o MDC de dois números é igual ao MDC do menor número e a diferença entre os dois números.

Implementação e Lógica do Algoritmo

Uma implementação concisa do Algoritmo de Euclides utiliza o operador de módulo para encontrar o MDC:

def calcular_mdc(a, b):
   # Continua enquanto b não for zero
   while b:
       # Atualiza a e b com o valor de b e o resto da divisão de a por b
       a, b = b, a % b
   # Quando b se torna 0, a contém o MDC
   return a
 

Esta implementação explora a atribuição de tuplas do Python. Ao substituir iterativamente o número maior pelo resto da divisão dos dois números, até que o resto seja zero, o número restante (a) é o MDC.

Do MDC ao MMC

Com base no MDC, o mínimo múltiplo comum (MMC) pode ser facilmente calculado usando a seguinte relação:

def calcular_mmc(a, b):
   # O MMC é o produto de a e b dividido pelo MDC de a e b
   # A divisão inteira // garante um resultado inteiro
   return (a * b) // calcular_mdc(a, b)
 

Esta fórmula é válida porque, para quaisquer dois inteiros positivos a e b, o produto deles é igual ao produto de seu MDC e MMC.

Aplicações em Competições

• Crivos de Primos: São usados em problemas de determinação de primalidade, fatoração prima, cálculo da função totiente de Euler e outros problemas relacionados a números primos.
• Algoritmo de Euclides: É indispensável em problemas envolvendo aritmética modular, simplificação de frações e resolução de equações de congruência.

Como Começar com o Projeto ACM-ICPC-Preparation

Para começar a explorar as implementações desses algoritmos, você pode clonar o repositório do projeto:

git clone https://gitcode.com/gh_mirrors/ac/ACM-ICPC-Preparation
 

O projeto é organizado semanalmente, com subdiretórios para solutions (soluções de problemas) e vanilla\_implementations (implementações básicas de algoritmos), facilitando um aprendizado progressivo.