Skip to content

Rozkład liczby na czynniki pierwsze

Posted in Nauka, and Programowanie

Na stronie Centralnej Komisji Egzaminacyjnej ( CKE ) możemy znaleźć wykaz algorytmów, których znajomość jest wymagana. Ostatnio pisałem na temat algorytmu, który sprawdza, czy dana liczba jest liczbą pierwszą. Wpis postanowiłem udostępnić na wykop.pl i zauważyłem, że wywołał on dyskusję, mimo że nie wypadł pozytywnie pod kątem ocen ( 3x wykop / 8x zakop ) ale akurat to mało istotne. Dziś poruszę kolejny algorytm jakim jest umiejętność rozkładu danej liczby na czynniki pierwsze.

Przestrzegam, aby uniknąć specyficznych komentarzy …

Algorytm został przygotowany na liczby, przy których komputer się nie napoci- jeżeli jesteś naprawdę dobry w te klocki pozostaw w komentarzu swoją opinię ale oprócz tego lepszy, bądź ciekawszy sposób rozwiązania, który będzie dobry dla komputera przy obliczaniu nawet 3^758930-2.

Zaczynając od teorii …

Czynnik pierwszy liczby naturalnej, to dowolna liczba pierwsza, która dzieli tę liczbę.
„Jedna z podstawowych obserwacji dotyczących liczb naturalnych mówi, że każda liczba naturalna większa od 1 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy. Wynika stąd dalej, że każda liczba naturalna większa od 1 jest pierwsza, lub daje się zapisać w postaci iloczynu liczb pierwszych.

 

Rozkład liczby naturalnej na czynniki pierwsze jest bardzo złożony obliczeniowo, co stanowi podstawę kryptografii asymetrycznej (patrz np. klucz RSA).”

~ Wikipedia.pl
Jak widzę, to kolejny już dosyć złożony obliczeniowo algorytm- no cóż, mówi się trudno.
Rozwiązanie
Schemat krokowy
1.Podaj liczbę naturalną n.
2.Jeżeli n>1 wtedy
zmienna pomocnicza i=1
dopóki i<=pierwiastek kwadratowy z n
dopóki !(n mod i)
wypisz „i * ”
jeżeli n=1 przerwij, a i zwiększ o 1
w przeciwnym wypadku
wypisz „niewłaściwe dane” i zakończ algorytm
Algorytm w C++

 

Be First to Comment

Dodaj komentarz

%d bloggers like this: