U lekciji Matematički algoritmi I u programu za faktorizaciju broja, je postavljen uslov da se traže delioci koji su manji od sqrt(n), ali to nije tačno, npr. faktor broja 10 je 5, ali je 5 > sqrt(10), tako da ga taj algoritam ne bi pronašao. Otkucao sam vaš algoritam u C++, ali ručno proveravajući neke primere se moja pretpostavka potvrdila. Molim vas za objašnjenje ili ispravku algoritma. Takođe ni algoritam za proveru prostih brojeva neće proveriti broj ako je manji od 25 (postavljeno je da je (6k - 1) * (6k - 1) <= n, a k = 1 tako da je to u startu uslov 25 > n.
Prvi algoritam:
Za faktorizaciju se ide do √n.
Ako broj 5 deli 10, onda je peticin “par” 10/5 tj. 2.
Ta dvojka se nalazi u intervalu [2, √n]
Ako neki broj n nema delioce u intervalu [2, √n], onda sigurno nema delioce ni u intervalu [√n, n], jer se u drugom intervalu nalaze “parovi” prvog intervala. Ako je 10 deljivo sa 2, onda je sigurno i deljivo sa 5.
Drugi algoritam:
(6k - 1) * (6k - 1), za k = 1 je jednako 25. Posto je 25 <= 25, program ulazi u while petlju. Sada treba da se proveri ovo:
06 if (n mod (6k–1) = 0) or (n mod (6k + 1) = 0) then
Posto je prvi uslov (n mod (6k - 1) == 0) zadovoljen (25 mod 5 == 0), onda program ide dalje, tj. vraca false sto znaci da 25 nije prost broj.