Boucling

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

23 messages

Mise à jour: il y a 4 mois

1
OP
PI

PoiIDeFesses

il y a 4 mois

Alors voilà l'énoncé :

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

Donnez votre réponse modulo 500500507.

Autant vous dire que la méthode bruteforce je peux l'oublier direct https://image.noelshack.com/fichiers/2018/10/1/1520256134-risitasue2.png
Quelqu'un a une piste ? Une formule ? https://image.noelshack.com/fichiers/2017/05/1486215313-sans-titre-20-5.png

RA

Ragedegland

il y a 4 mois

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 https://image.noelshack.com/fichiers/2021/32/7/1629030511-1499374046-risistasgroschefdoigt.png

OP
PI

PoiIDeFesses

il y a 4 mois


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 https://image.noelshack.com/fichiers/2021/32/7/1629030511-1499374046-risistasgroschefdoigt.png

C'est un problème sur la platforme Project Euler et je galère dessus, si je trouve pas je regarderais la solution https://image.noelshack.com/fichiers/2017/11/1489419617-sans-titre-5.png

VL

vladvolvodsky

il y a 4 mois

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.

MI

mirobolan

il y a 4 mois

Ah le probleme 500, j'avais galéré dessus et j'avais jamais trouvé. Demande à Motocultage si il passe par là

CD

cdine

il y a 4 mois

500500507

OP
PI

PoiIDeFesses

il y a 4 mois


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 https://image.noelshack.com/fichiers/2017/11/1489419617-sans-titre-5.png

MI

mirobolan

il y a 4 mois

De memoire le khey susmentionné m'avait suggéré d'utiliser un algorithme glouton joint à un sticker de pierre ménès

OP
PI

PoiIDeFesses

il y a 4 mois


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 https://image.noelshack.com/fichiers/2022/38/4/1663852709-golemabasourdi.png

[O

[OwO]

il y a 4 mois

ce problème qui sent le projet euler avant même que tu le dises

VL

vladvolvodsky

il y a 4 mois

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 https://image.noelshack.com/fichiers/2017/11/1489419617-sans-titre-5.png

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 ?

TL

TheLelouch4

il y a 4 mois

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

MO

MAKI_OTSUKI

il y a 4 mois

c'est le PGCD ou le PPCD

MB

MymyBE

il y a 4 mois

à ta place j'aurais abandonné khey

MI

mirobolan

il y a 4 mois

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é

OP
PI

PoiIDeFesses

il y a 4 mois

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 https://image.noelshack.com/fichiers/2022/38/5/1663921748-ahi.png

--

--HailSatan--

il y a 4 mois

Demande à ChatGPT

[O

[OwO]

il y a 4 mois

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 ?

OP
PI

PoiIDeFesses

il y a 4 mois


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 https://image.noelshack.com/fichiers/2017/05/1486215313-sans-titre-20-5.png

SK

SmartKontrakt

il y a 4 mois

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())
VL

vladvolvodsky

il y a 4 mois

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 https://image.noelshack.com/fichiers/2022/38/5/1663921748-ahi.png

Mec si tu veux progresser en algo c'est clairement pas ouf ce genre de problèmes. là la solution c'est un mélange de TDN et d'ingéniosité, y'a 0% d'algo là dedans .
Si tu veux progresser en algo (et en info en général), je te conseille TAOCP nofake c'est vraiment un excellent bouquin.

SK

SmartKontrakt

il y a 4 mois

Mec si tu veux progresser en algo c'est clairement pas ouf ce genre de problèmes. là la solution c'est un mélange de TDN et d'ingéniosité, y'a 0% d'algo là dedans .
Si tu veux progresser en algo (et en info en général), je te conseille TAOCP nofake c'est vraiment un excellent bouquin.

Excellent bouquin mais rien que pour le volume 1 tu peux réserver 6 mois dans une bibliothèque à bosser toute la journée

VL

vladvolvodsky

il y a 4 mois

Excellent bouquin mais rien que pour le volume 1 tu peux réserver 6 mois dans une bibliothèque à bosser toute la journée

Imo bien investis si tu veux apprendre à faire de l'algo
Après on rappelle : l'algo est littéralement le pire domaine en info, c'est inintéressant et la recherche là dedans est juste totalement useless

VL

vladvolvodsky

il y a 4 mois

Je suis un hater de rust, mais bon t'as un peu raison. Reste que 99% de la recherche qui veut faire baisser de 0.01% l'exposant de la complexité asymptotique d'un problème est profondément useless
En ce moment j'etudie les produits de matrice et nofake les mecs passent 40 piges de recherche pour passer en O(n^k-0.002) au lieu de O(n^k), c'est juste délirant
Sans parler de l'algo des graphes qui s'adresse souvent à des problèmes INEXISTANTS, de l'algo du texte ou les mecs résolvent le même problème en boucle comme pour le produit de matrices, voire de l'algo olympique où les mecs inventent carrément des problèmes pour les résoudre eux même

O5

op500

il y a 4 mois

demande a chatgpt et fait pas chier