Python feladat : amit elakarok érni az, hogy n=lehet bármilyen szám annak az osztóit szeretném kiírni ?

"Aki azt állítja, hogy sqrt(n)-ig menve nem oldható meg a feladat, az téved."

Nem, igazuk van: gyök-n-ig megtaláljuk a szám összes prím osztóját. Az összes prím osztó ismeretében előállítható az összes osztó. Igaz, ez egy elég komplikált kombinatorikus feladat.

Én valami olyasmivel próbálkoznék, hogy elkezdem maradékosan osztani a számot egyre nagyobb prímekkel. Ezzel meglenne a szám prímtényezőkre osztása, ha van a prímszámokról listánk, akkor ez nagyon, nagyon gyors lenne. Ezután a prímszámok kombinációja megadná az összes osztót. Kíváncsi vagyok, hogy ez a módszer mikortól kezdve lenne gyorsabb. Nagy számoknál nagyon-nagy lehet a különbség.

"Aki azt állítja, hogy sqrt(n)-ig menve nem oldható meg a feladat, az téved."

ha! Nem megy a szövegértés úgy látszik. :D

Baszki ez egy józan paraszti ésszel megoldható feladat sqrt(n) komplexitással, nem tudom miért kevernek bele egyesek prímtényezőket.

Ha A szám osztója X, akkor a szám nyilván felírható A = X * Y alakban, ahol Y is osztója lesz. Innen csak át kell rendezni az egyenletet, hogy megkapjuk Y-t.

Az is nyilvánvaló, hogy nem kell sqrt(n)-nél tovább vizsgálni, mert az a fölötti értékek csak önmaguknál kisebb számmal szorozva lehetnének megoldások, de a kisebb számokat már megvizsgáltuk az előző lépésekben.

Puszta kíváncsiságból írtam egy scriptet, ami 775,514,817-nek 1.3s alatt visszatér az összes osztójával. Kíváncsi vagyok más megoldások hogyan teljesítenek. Akit érdekel: [link]

(mondjuk volt egy kb 30sec, mire letölti az első 50M primet :D)

#39 az kifejezetten hulladék futásidőnek és valami szuboptimális megoldásnak tűnik, de nincs hozzáférésem a google drive linkhez.

Miért nem dobod fel pastebin-re?