L'Atelier Monstre

Énoncé du problème Soit une fonction f définie pour tout entier positif n vérifiant : ∑d|n f(d) = n Étant donnés n entiers a1, a2, …, an, calculer ∑i=1n f(ai). Méthode de résolution La fonction f n'est autre que l'indicatrice d'Euler φ. Elle possède les propriétés suivantes : Si q = nm avec n et m premiers entre eux, alors f(q) = f(n) × f(m). ...

Crible linéaire L'objectif est de déterminer tous les nombres premiers jusqu'à une borne \(n\), avec \(n \le 10^8\). Le crible d'Ératosthène classique a une complexité de \(O(n \ln \ln n)\), car il marque les multiples de chaque nombre premier à plusieurs reprises. Pour une efficacité optimale, on utilise un crible linéaire où chaque nombre com ...