PROBLÈME DE MATH IMPOSSIBLE à RESOUDRE en PYTHON :sueur:

Alors voilà l'énoncé :

Le nombre de diviseurs de 120 est 16.

En fait, 120 est le plus petit nombre ayant 16 diviseurs.

Trouvez le plus petit nombre ayant 2^500500 diviseurs.

Donnez votre réponse modulo 500500507.

Autant vous dire que la méthode bruteforce je peux l'oublier direct
Quelqu'un a une piste ? Une formule ?

Le 27 novembre 2024 à 00:59:11 :
La réponse de la calcul est très simple surtout en puton alors voilà il faut écrire une formule qui permet au soustracteur divisionel de swap ton calcul pour le diviser en parti exacte en créant une boucle qui pète

C'est un problème sur la platforme Project Euler et je galère dessus, si je trouve pas je regarderais la solution

Le 27 novembre 2024 à 01:01:40 :
L'Op :
Si ton nombre a des diviseurs premiers, par lemme de Gauss le produit de deux diviseurs premiers est premier. 500500507=13 × 38500039, t'as que 2 facteurs premiers, donc tu peux ajouter arbitrairement ces facteurs dans ton produit de nombres premiers sans changer le modulo de ta réponse..
T'as quasiment tout là, plus qu'à rédiger.

OK attend ça a l'air d'être une bonne piste ça
Je vais relire ce que tu as dit au calme et tenter une approche

Le 27 novembre 2024 à 01:03:10 :
Ah le probleme 500, j'avais galéré dessus et j'avais jamais trouvé. Demande à Motocultage si il passe par là

Ah je ne pensais pas que le forum connaissait je suis surpris

Le 27 novembre 2024 à 01:03:58 :

Le 27 novembre 2024 à 01:01:40 :
L'Op :
Si ton nombre a des diviseurs premiers, par lemme de Gauss le produit de deux diviseurs premiers est premier. 500500507=13 × 38500039, t'as que 2 facteurs premiers, donc tu peux ajouter arbitrairement ces facteurs dans ton produit de nombres premiers sans changer le modulo de ta réponse..
T'as quasiment tout là, plus qu'à rédiger.

OK attend ça a l'air d'être une bonne piste ça
Je vais relire ce que tu as dit au calme et tenter une approche

J'ai pas rédigé le truc en entier, mais je suis quasi certain que c'est suffisant.
PS : tu fais quoi dans la vie ? Qu'est-ce qui t'amène à faire le projet Euler ?

Ah je ne pensais pas que le forum connaissait je suis surpris

Tu crois quoi c'est l'elite ici j'avais tryhard un peu le site a l'epoque mais ca fait des années que j'y ai pas touché

Le 27 novembre 2024 à 01:06:05 :

Le 27 novembre 2024 à 01:03:58 :

Le 27 novembre 2024 à 01:01:40 :
L'Op :
Si ton nombre a des diviseurs premiers, par lemme de Gauss le produit de deux diviseurs premiers est premier. 500500507=13 × 38500039, t'as que 2 facteurs premiers, donc tu peux ajouter arbitrairement ces facteurs dans ton produit de nombres premiers sans changer le modulo de ta réponse..
T'as quasiment tout là, plus qu'à rédiger.

OK attend ça a l'air d'être une bonne piste ça
Je vais relire ce que tu as dit au calme et tenter une approche

J'ai pas rédigé le truc en entier, mais je suis quasi certain que c'est suffisant.
PS : tu fais quoi dans la vie ? Qu'est-ce qui t'amène à faire le projet Euler ?

J'ai finis mes études d'info et je cherche mon premier taff. En attendant je passe le temps en faisant ça car j'ai des lacunes en algorithmie

Le 27 novembre 2024 à 01:07:40 :

Ah je ne pensais pas que le forum connaissait je suis surpris

Tu crois quoi c'est l'elite ici j'avais tryhard un peu le site a l'epoque mais ca fait des années que j'y ai pas touché

tu fais quoi mirobolan maintenant t'étais à Ulm non ?

Le 27 novembre 2024 à 01:06:26 :
Faut chercher les plus petits premiers qui marchent dans la décomposition facteur premier et boucler pour avoir les exposants.
Puis tu prend le modulo de leur produit

Ok toi aussi tu me parles des nombres premiers, alors je vais tester avec ce que ma dit le premier khey et si je trouve pas je regarderais en détail ce que tu m'as dit

import heapq

def solve():
    T, M = 500500, 500500507
    L = 7376507
    sieve = [1] * (L + 1)
    for i in range(2, int(L**0.5) + 1):
        if sieve[i]:
            for j in range(i * i, L + 1, i):
                sieve[j] = 0
    primes = (i for i, p in enumerate(sieve) if p and i > 1)
    h, r = [next(primes)], 1
    for _ in range(T):
        x = heapq.heappop(h)
        r = r * x % M
        heapq.heappush(h, x * x)
        if len(h) < T:
            heapq.heappush(h, next(primes))
    return r

print(solve())