Arytmetyka to jeden z najstarszych i najlepiej poznanych przez ludzkość działów matematyki. Opisuje ona zasady podstawowych działań i operacji na liczbach, w związku z czym każdy z nas ma z nią do czynienia praktycznie na co dzień. Arytmetyka odgrywa również ważną rolę w informatyce. Jednym z algorytmów wymagających użycia jej podstawowych praw jest rozkład liczby na czynniki, któremu dzisiaj przyjrzymy się dokładniej.
Rozkład liczby na czynniki to inaczej wypisanie wszystkich liczb pierwszych, których iloczyn da nam początkową liczbę. O tym, czym jest liczba pierwsza i jak sprawdzić, czy dowolna liczba n nią jest, przeczytasz dokładniej tutaj. Jak wspominałem w załączonym artykule — każdą liczbę naturalną większą niż 1 można rozłożyć na czynniki pierwsze. Jak rozłożyć dowolną liczbę na czynniki pierwsze? Poniżej znajdziesz odpowiedź na to pytanie, a także implementacje w dostępnych na maturze językach: Java, C++ i Python.
Nie daj się zaskoczyć na maturze – zapisz się do listy mailingowej już teraz!
Algorytm rozkładu na czynniki
Zanim przejdziemy do faktycznego tworzenia programu, musimy najpierw ustalić algorytm, według którego będzie on działać. Na początku pobieramy liczbę naturalną n od użytkownika. Następnie tworzymy pętlę, w której ustawiamy zmienną iterującą i na 2 (najmniejsza liczba pierwsza, od niej musimy rozpocząć) i sprawdzamy co krok, czy zmienna n jest większa lub równa 2 — 0 i 1 w wyniku dzielenia nie dadzą liczby pierwszej, więc je pomijamy. Następnie co iterację sprawdzamy, czy n jest podzielna przez i (reszta z dzielenia równa 0). Jeżeli tak, to dzielimy n przez i, wypisujemy jej czynnik i, a potem powtarzamy tą procedurę aż do momentu, w którym n nie będzie podzielne przez i. Następnie w tym samym kroku iteracji zwiększamy zmienną iteracyjną o 1. Dzięki temu liczba n będzie sukcesywnie zmniejszana w wyniku dzielenia przez jej czynniki, co doprowadzi do końca pętli. Jako że wypisaliśmy wszystkie czynniki liczby n, jednocześnie pomijając jedynkę, musimy ją również na koniec algorytmu wypisać. Do sprawdzania podzielności liczb w większości języków programowania można wykorzystać operator % (modulo) — jeżeli a % b jest równe zero, to oznacza, że a jest podzielna przez b. Przebieg algorytmu przestawiłem na schemacie blokowym poniżej:
Rozkład liczby na czynniki — implementacja C++, Java, Python
Mamy już zasadę działania naszego programu — pora na (najbardziej) przyjemny etap życia programisty — implementację. Decydując się na maturę z informatyki do wyboru masz jeden z trzech języków programowania: Javę, C++ lub Pythona. W związku z tym postanowiłem przygotować implementację w każdym z tych języków. W implementacjach zamieściłem także komentarze, abyś mógł lepiej zrozumieć, co się w nich dzieje.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
//program rozkładający liczbę na czynniki //Kosiński Łukasz #include <iostream> #include <cmath> using namespace std; void rozloz(unsigned a) { cout << a << "="; for(int i=2; a>=2;)//ustawiamy zmienną sterującą na 2, bo jest to pierwsza z liczb pierwszych { while(a%i==0)//jeśli liczba jest podzielna przez sterującą to wypisana zostanie liczba pierwsza, a parametr podzielony { cout << i << " "; a/=i; } i++;//w przeciwnym wypadku inkrementujemy "i" } cout << "1" << endl; } int main() { int x; do { cin >> x; rozloz(x); }while(x!=0);//pętla bedzie się wykonywać dopóki nie wpiszemy zera return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
import math #potrzebny import def rozloz(x): #definiujemy funkcje do późniejszego użycia print(str(x) + " = "), k = 2 # ustawiamy zmienna pomocnicza, oznaczajaca aktualny dzielnik while x >= 2: # dopoki x nie przyjmie wartosci mniejszej niz 2 while x % k == 0: # dopoki x bedzie podzielny przez zmienna pomocnicza print(str(x) + " "), #wypisz ja do konsoli x = int(x/k) # a nastepnie zapisz wynik dzielenia k += 1 #co kazda iteracje zwieksz zmienna pomocnicza o 1 print("1") #wypisz 1 na koniec - dzielnik kazdej liczby print("Program rozkladający liczbę na jej czynniki.") print("Podaj liczbę: ") a = int(input()) rozloz(a) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
package matura; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //Inicjalizacja Scannera pobierajacego zmienne od uzytkownika int liczba = sc.nextInt(); //Pobieramy liczbę którą chcemy sprawdzić System.out.print(liczba + " = "); for(int i=2; liczba>=2;) { //ustawiamy zmienną sterującą na 2, bo jest to pierwsza z liczb pierwszych while(liczba%i==0) { //jeśli liczba jest podzielna przez sterującą to wypisana zostanie liczba pierwsza, a parametr podzielony System.out.print(i + " * "); liczba /= i; } i++; //nastepnie inkrementujemy "i" } System.out.print(1); //wypisujemy na koniec jedynke sc.close(); //zwalniamy zasoby } } |
Pamiętaj, że rozkład liczby na czynniki jest tylko jednym z wielu wymaganych algorytmów na maturze z informatyki. Jeżeli przygotowujesz się do niej i chcesz to zrobić jak najlepiej, zachęcam cię do zapoznania się z poradami, które zamieściłem w tym poście. Znajdziesz tam również listę najważniejszych algorytmów i odnośniki do ich implementacji.
Krolos
says:Cześć, co sądzisz o takiej implementacji? Pozdrawiam.
#include
using namespace std;
int main()
{
int n;
cout<<"podaj liczbe do rozlozenia na czynniki"<>n;
cout<<"czynniki: "<<endl<<1<<endl;
for (int i=2;n!=1;)
{
if(n%i==0)
{
cout<<i<<endl;
n=n/i;
}
else
{
i++;
}
}
return 0;
}
Tycjan Sobel
says:Cześć, dość skomplikowana implementacja jak na tak prosty algorytm :), pozowoliłem sobie na mały refaktor. Niestety wklejanie kodu jako komentarz powoduje ucięcie niektórych znaków, przez co kod jest nie kompletny (chyba zabezpieczenie przed XSS w komentarzach) Niżej udostępniam link do gista 🙂
https://gist.github.com/mrtycjan/bb25dfcdb3c3a0623abd64d6f391b528
Łukasz Kosiński
says:Fajny kod fajny. Lepszy – złożoność mniejsza 😉 dobrze, że wpadłeś.
Jednooki
says:Cześć
Chciałbym się dowiedzieć za co odpowiada w kodzie ten zapis: a/=i;
Kod przekształciłem na taki i działa poprawnie. A także nie rozumiem zapisu w pętli for: a>=2. Dlaczego tak musimy to zapisać i jak to działa. Wiem że ta wartość jest to warunek kończący, ale dlaczego zapisujemy tam zmienną a. https://uploads.disquscdn.com/images/27d2ed7e5393ad8945a8e5c4d3002530238aecf415fec4bbfdde69d4463ca201.png
Łukasz Kosiński
says:Taki zapis jest równoważny z zapisem a=a/i; Zmiennej a przypisujemy wartość równą ilorazowi a przez i.
Dlaczego robimy coś takiego? Może wytłumaczę na przykładzie. Masz liczbę 28. W pierwszym kroku program sprawdza, czy 28 jest podzielne przez 2. Jest więc dzielimy 28 na dwa i w rezultacie otrzymujemy 14. 14 również jest podzielne przez 2, dzielimy i otrzymujemy 7. 7 już nie jest podzielne przez 2 dlatego i będzie rosło o 1 do momentu, aż znajdzie dzielnik siódemki. Dzielnikiem siódemki jest tylko 7, więc dzielimy 7 przez 7 i otrzymujemy 1. To już jest mniejsze od naszego warunku, dlatego kończymy wykonywanie pętli.
Jednooki
says:O faktycznie! Dzięki wielkie za wytłumaczenie! Wielki plus 🙂
Łukasz Kosiński
says:Gdybyśmy nie dzielili liczby przez napotkany czynnik to wtedy mielibyśmy taką sytuację, że i w pętli for dojdzie do np. czwórki. 28 jest podzielne przez cztery, ale przecież nie jest liczbą pierwszą.
W warunku natomiast napisałem a>= ponieważ dwójka jest najmniejszą z liczb pierwszych, a wykonując stopniowo to dzielenie, o które najpierw spytałeś a się zmniejsza. Dla 28 a przyjmuje wartości 28, potem 14, potem 7 i w końcu 1. Jedynka jest mniejsza od najmniejszej znanej liczby pierwszej, dlatego na pewno nie będzie miała czynnika, będącego liczbą pierwszą. Mam nadzieję, że trochę ci rozjaśniłem 🙂