Lançado · em melhoria
Algorithm
MDC e MMC, aritmética modular e inversos, exponenciação rápida, crivo de Eratóstenes e nCr mod p: a teoria dos números para algoritmos.
A teoria dos números estuda os inteiros, principalmente a divisibilidade e os restos. Em algoritmos, isso significa calcular o MDC e o MMC com o algoritmo de Euclides, lidar com valores enormes por meio da aritmética modular e encontrar inversos modulares com o algoritmo de Euclides estendido ou o pequeno teorema de Fermat. A exponenciação rápida, o crivo de Eratóstenes, a fatoração em primos e os coeficientes binomiais módulo um primo completam a caixa de ferramentas.
Essas ferramentas aparecem o tempo todo em entrevistas técnicas e maratonas de programação como "imprima a resposta módulo 10^9 + 7", e em produção sustentam a criptografia de chave pública como RSA e Diffie-Hellman, funções hash, geradores de números aleatórios e dígitos verificadores. Quase todas rodam em tempo logarítmico ou quase linear, então entendê-las transforma cálculos que nunca terminariam em operações de milissegundos.
Comece acompanhando à mão as regras da aritmética modular e o algoritmo de Euclides, depois implemente você mesmo a exponenciação rápida e o crivo. Em seguida, passe para inversos modulares e nCr mod p; se você programa em C++ ou Java, pratique o tratamento de overflow em multiplicações e de restos negativos. Aprenda também as funções padrão, como pow(a, e, m) e math.gcd do Python.
Repetir mdc(a, b) = mdc(b, a mod b) encontra o MDC em O(log n); a versão estendida também devolve os coeficientes de ax + by = mdc(a, b).
Soma, subtração e multiplicação preservam os restos, então você reduz a cada passo; a divisão vira multiplicação por um inverso modular.
Elevar a base ao quadrado seguindo os bits do expoente calcula a^e mod m com cerca de log e multiplicações em vez de e.
Riscar os múltiplos de cada primo a partir de i × i encontra todos os primos até n em O(n log log n); uma tabela do menor fator primo permite fatorar rapidamente.
gcd calcula o máximo divisor comum com o algoritmo de Euclides, e o MMC sai como a // gcd(a, b) * b. mod_pow é a exponenciação rápida: percorre os bits do expoente elevando ao quadrado e multiplicando, e com um módulo primo p, a^(p-2) dá o inverso modular de a. sieve usa o crivo de Eratóstenes para listar todos os primos até 30. Salve o arquivo e execute python number_theory.py.
number_theory.py
import math
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a
def mod_pow(base: int, exp: int, mod: int) -> int:
result, base = 1 % mod, base % mod
while exp > 0:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
def sieve(n: int) -> list[int]:
is_prime = [False, False] + [True] * (n - 1)
for i in range(2, math.isqrt(n) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i, p in enumerate(is_prime) if p]
MOD = 10**9 + 7
print(gcd(84, 36), 84 // gcd(84, 36) * 36) # 12 252
print(mod_pow(3, 200, 13)) # 9
print(mod_pow(3, MOD - 2, MOD)) # 333333336, the inverse of 3
print(sieve(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
python number_theory.pySeis capítulos que levam você da instalação aos conceitos essenciais de Matemática e teoria dos números.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Matemática e teoria dos números.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.