Hogyan tudom kiszámolni hogy egy számnak hány darab osztója van?

vhogy igy: Határozzuk meg 60 osztóinak a számát!

Írjuk fel a prímhatványtényezős alakját!

60= 22 * 3 * 5 = 22 * 31 * 51

A kitevők: 2; 1; 1

Növeljük mindegyiket 1-gyel, majd a kapott összegeknek vegyük a szorzatát!

(2 + 1) * (1 + 1) * (1 + 1) = 3 * 2 * 2 = 12

A 60-nak 12 darab osztója van.

2.

Határozzuk meg 756 osztóinak a számát!

Írjuk fel a prímhatványtényezős alakját!

756 = 22 * 33 * 7 = 22 * 33 * 71

A kitevők: 2; 3; 1

Növeljük mindegyiket 1-gyel, majd a kapott összegeknek vegyük a szorzatát!

(2 + 1) * (3 + 1) * (1 + 1) = 3 * 4 * 2 = 24

A 756-nak 24 darab osztója van.

3.

Határozzuk meg 49 osztóinak a számát!

Írjuk fel a prímhatványtényezős alakját!

49 = 7 * 7 = 72

A kitevő: 2

Növeljük 1-gyel!

(2 + 1) = 3

A 49-nek 3 darab osztója van.

[link]

A fentebbi linkben megtalálod, hogy kell felírni a prímtényezők ismeretében az osztószámot.

Ha a vizsgált szám prímtényezőit ismered, akkor ugye

n=(elsőprím^valahanyadikon)*(második prím^valahanyadikon)*... (sokadik prím^valahanyadikon) összefüggést fel lehet írni.

Ekkor az osztószám

"d(n)" = (első kitevő+1)*(második kitevő+1)*.... (sokadik kitevő+1)

Az osztószám tartalmazza az 1-et, és önmagát is!

Pl. ha n=6 akkor 6=1^0*2^1*3^1

Ekkor d(n)= (1+1)*(1+1)=4

Tehát ha a szám prímtényezői ismertek, akkor felírható a szám osztóinak száma is.

A baj ott van, hogy jelenleg nem ismert olyan eljárás, amivel egy tetszőlegesen nagy szám rövid idő alatt prímtényezőre bontható.

Ez az alapja a ma használt internetes titkosításnak is, vagyis hogy nem ismert hatékony prímfaktorizáló algoritmus.(Hogy van e ilyen , ha jól tudom nem bizonyított hogy nem létezhet, de egyelőre nem ismert.)

Ui.: Persze pár jegyű számok esetén egy számítógép vagy ember gyorsan megmondja a prímtényezőket, de a számjegyek növelésével exponenciálisan nő a PC gondolkodási ideje.

Még akkor is, ha n prímtényezőre bontásánál elegendő minden négyzetgyök(n)-nél kisebb számot megvizsgálni.

100 esetén pl. sqr(100)=10 alatti számokkal elég próbálkozni. Tehát:

100/1=100

100/2=50

50/5=10

10/5=2

2/2=1

Látható hogy sqr(n)-nél kisebb számokkal elég próbálkozni.

Ez esetben ugye:

n(100)= 1^0*2^2*5^2

d(n)= (0+1)*(2+1)*(2+1)=9

{1,2,4,5,10,20,25,50,100}=9