Rozkład liczby na czynniki

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.

 

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.

//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;
}

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)

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.