Hogy lehet hatékonyan megtalálni azt a számot amelyiknek a legtöbb osztója van egy adott tartományon belül?
Adott egy intervallum 1 és n között (n is beletartozik).
Triviálisan az összes számra osztópróbával az összes számra kiszámolni az összes osztójának számát és az egészre egy maximum keresés.
Tudjuk azonban hogy prímtényezős felbontással meg lehet tudni az osztók számát. Pl.: a^x * b^y * c^z a prímtényezős felbontása egy számnak akkor (x+1)*(y+1)*(z+1) darab osztója van. Az is biztos, hogy a legkisebb szám melynek 1000 darab osztója van az a 19 683 000 000 000 a nélkül hogy eddig a naiv módszerrel végigpróbáltuk volna az összes számot eddig. Hiszen ez pont 2^9 * 3^9 * 5^9.
válasza:Valami backtrack (visszalépéses keresés) algoritmussal lehet, hogy nagyon sokat tudsz nyerni, és tényleg csak minimális mennyiségű esetet kell végignézned. (Én mindenesetre nem látom, hogy hogyan.)
SZVSZ amúgy ez a kérdés a számítástechnológia kategóriába jobban illik, mint a tudományokba.
válasza:#10: "Ez biztos igaz?"
Biztos, nézz meg HCN-listát, pl.:
alul 124260 HCNs, lista-magyarázat. Részlet:
...
2301.566072 247.2997962 335 15 10 6 5 4 3^4 2^13 1^313
2301.655807 247.3222691 334 15 9 6 5 4 3^4 2^15 1^310
2301.838129 247.3240532 334 16 10 5^2 4 3^4 2^15 1^310
2301.918171 247.3267234 334 14 9 5^2 4^2 3^3 2^15 1^310
2301.943489 247.3346916 334 17 8 6 5 4 3^4 2^15 1^310
2302.061272 247.3530408 334 14 10 6 5 4 3^4 2^15 1^310
2302.247243 247.3630911 335 14 9 6 4^2 3^4 2^14 1^312
2302.348954 247.3828937 334 16 9 6 5 4 3^4 2^15 1^310
2302.488405 247.3868076 335 15 9 6 5 3^5 2^14 1^312
2302.572098 247.3912620 334 14 9 7 5 4 3^4 2^15 1^310
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!