Doido Dev

Princípio A dceomposição em fatores primos de um inteiro é feita por divisões sucessivas (trial division). Complexidade \(O(\sqrt{n})\) ou, com otimizações, \(O\left(\frac{\sqrt{n}}{\ln(\sqrt{n})}\right)\). Fatoração de um fatorial \(N!\) Dado um inteiro \(N\), decomponha \(N!\) em fatores primos e exiba cada base \(p_i\) com seu respectivo ex ...

Pré-requisito - Blocagem de Divisão Problema Dado um número $ n $, calcule: $$ \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor $$ Abordagem e Código Este somatório pode ser calculado em tempo $ \mathcal{O}(n) $. Para otimizar, observe que para valores grandes de $ n $, muitas frações $ \lfloor n/i \rfloor $ terão o mesmo valor. Por exemplo, para $ n ...

Introdução à Função Totiente de Euler A Função Totiente de Euler, denotada como φ(n), determina a contagem de inteiros positivos entre 1 e n que são coprimos com n (ou seja, seu máximo divisor comum é 1). Esta função é uma ferramenta fundamental na teoria dos números e possui propriedades multiplicativas, como φ(a·b) = φ(a)·φ(b) quando a e b sã ...