Znajdź rozkład na czynniki pierwsze liczb

[Bran]

Znajdź rozkład na czynniki pierwsze następujących liczb:

a) \(\displaystyle{ 443}\)
b) \(\displaystyle{ 11 \; 849}\)
c) \(\displaystyle{ 6 \; 967 \; 664}\)
d) \(\displaystyle{ 61 \; 930 \; 099}\)

Wiem, że pierwsza liczba jest liczbą pierwszą udało mi się to wykazać z algorytmu Eratostenesa.

Z cech podzielności widać, że liczba z punktu c) jest podzielna przez \(\displaystyle{ 4}\), a zatem: \(\displaystyle{ 6 \; 967 \; 664 = 4 \cdot 1 741 916}\) sytuacja się powtarza: \(\displaystyle{ 6 \; 967 \; 664 = 4 \cdot 4 \cdot 435 479}\) Zauważmy, że \(\displaystyle{ 660^2 - 11^2 = 435 479}\), więc jest równe: \(\displaystyle{ (660-11)(660+11) = 649 \cdot 671}\)

A potem już łatwo z sita Eratostenesa: \(\displaystyle{ 649 = 11 \cdot 59}\), \(\displaystyle{ 660 = 11 \cdot 61}\)

Zatem: \(\displaystyle{ 6 \; 967 \; 664 = 2^4 \cdot 11^2 \cdot 59 \cdot 61}\)


Natomiast nie mam pomysłu na pozostałe liczby, męczenie się z algorytmem Eratostenesa, to katorga (?) - z algorytmu Fermata też nie udało mi się nic ciekawego wyznaczyć. Pomyślałem sobie, że można próbować kolejno dzielić przez liczby pierwsze (czyli sito), ale pomyślałem sobie - co jeśli nie miałbym kalkulatora, a to jest iloczyn dwóch dużych liczb? Więc zamiast ryzykować - spytam: Czy jest jakiś sposób na wyznaczenie takiego rozkładu?

[a4karo]

Wolfram i polecenie factorize

[Gosda]

Ja bym jednak spróbował dzielić przez małe liczby, \(61930099 = 7 \cdot 11^3 \cdot 17^2 \cdot 23\) ma same małe dzielniki pierwsze. Nie ma nic wstydliwego w zrobieniu odrobiny rachunków, szczególnie że dwa pierwsze czynniki można zgadnąć cechami podzielności (mało znane, ale są).

Swoją drogą, sito tam na początku to przesada, można elementarniej: \( 660^2 - 11^2 = 11^2 \cdot (60^2 - 1) = 11^2 \cdot 59 \cdot 61 \).