Note que se $$gcd(a, b) \neq 1$$ então $$a$$ e $$b$$ possuem algum fator primo em comum. Usando o fato de que entre $$1$$ e $$N$$ um número $$p$$ divide exatamente $$\frac{N}{p}$$ (divisão inteira) números. Então, podemos calcular o conjunto $$P$$ de primos que dividem $$N$$ e depois somamos todas as divisões inteiras para cada primo de $$P$$, porém, alguns primos podem acabar dividindo o mesmo número, ou seja, no final o nosso código vai contar o mesmo número duas vezes. Por exemplo:
Se $$N = 10$$, então $$P = {2, 5}$$. $$2$$ divide os números $$2, 4, 6, 8, 10$$ e $$5$$ divide os números $$5, 10$$. Note que $$\frac{10}{2} + \frac{10}{5} = 7$$ quando na verdade a resposta é $$6$$. Isso se dá por que o número $$10$$ foi contado duas vezes.
Então como resolver esse problema de que os números podem acabar sendo contados várias vezes? Simples, usando o princípio da inclusão-exclusão que diz, dados dois conjuntos $$A$$ e $$B$$:
$$A \cup B = A + B – A\cap B$$
Então, para os dois conjuntos do exemplos, se $$A$$ for o conjunto dos múltiplos de $$2$$ menores ou iguais a $$N$$ e $$B$$ o de $$5$$ então
$$A \cup B = A + B – A \cap B \ \implies A\cup B = \frac{10}{2} + \frac{10}{5} – \frac{10}{10} = 6$$
Portanto, basta calcular todos os primos divisores de $$N$$ usando o algoritmo do crivo de Eratóstenes, já que $$N \leq 10^6$$, e depois usar inclusão-exclusão nos primos que o dividem.
Código para melhor entendimento:
https://gist.github.com/lawrencefmm/f1af0ada8f3ffd8ee0715b9cf4956b41
Deixe um comentário