Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

Rozkład liczby na czynniki pierwsze


powrót

Zacznijmy od definicji. Rozkład liczby naturalnej n>1 na czynniki pierwsze polega na przedstawieniu jej w postaci iloczynu liczb pierwszych.

Liczby złożone będą miały co najmniej dwa czynniki pierwsze. Liczby pierwsze się nie rozkładają. Problem rozwiążemy sposobem szkolnym. Popatrzmy najpierw na kilka przykładów. Rozłóżmy liczby 24, 100, 1520:

$$24=2\cdot 2\cdot 2 \cdot 3$$

$$100=2\cdot 2\cdot 5 \cdot 5$$

$$1520=2\cdot 2\cdot 2 \cdot 2 \cdot 5 \cdot 19$$

Liczbę do rozłożenia będziemy dzielić przez liczby pierwsze tak długo, aż z liczby rozkładanej zrobi się 1.

prime

prime

prime

Rozpoczynamy od dwójki - jest to pierwsza liczba pierwsza. Jeśli rozkładana liczba dzieli się bez reszty przez 2, to wypisujemy 2 i skracamy ją przez 2. Czynność powtarzamy tak długo, jak długo liczba dana liczba jest podzielna przez 2. W drugim kroku szukamy następnego dzielnika rozkładanej liczby. Będzie to następna liczba pierwsza. Czynności te powtarzamy do momentu uzyskania wartości 1.

Zakładamy, że liczba, która znajdzie się na wejściu będzie większa od jedynki.

Rozwiązanie w C++:

/**********www.algorytm.edu.pl*****************/
#include<iostream>
using namespace std;
 
int main()
{
    int n;
        
        cout<<"Podaj liczbę: ";
        cin>>n;
        
        cout<<"Czynniki pierwsze liczby "<<n<<": ";
        
        int k=2; //ustawiamy k na pierwszą liczbę pierwszą

        //rozkład liczby na czynniki pierwsze
        while(n>1)
        {
                while(n%k==0) //dopóki liczba jest podzielna przez k
                {
                        cout<<k<<" ";
                        n/=k;
                }
                ++k;
        }
        
        return 0;
}

Program można znacznie zoptymalizować szukając dzielników tylko do pierwiastka z liczby n (w tym miejscu jest wyjaśnione dlaczego). Poniżej algorytm optymalny:

#include<iostream>
#include<cmath>
using namespace std;
 
int main()
{
    int n, pierw, pom;
 
        cout<<"Podaj liczbę: ";
        cin>>n;
        
        pierw = sqrt(n);
 
        cout<<"Czynniki pierwsze liczby "<<n<<": ";
 
        int k=2; //ustawiamy k na pierwszą liczbę pierwszą
 
        //rozkład liczby na czynniki pierwsze
        while(n>1&&k<=pierw)
        {
                while(n%k==0) //dopóki liczba jest podzielna przez k
                {
                        cout<<k<<" ";
                        n/=k;
                }
                ++k;
        }
        
        if(n>1)
               cout<<n;
        cout<<endl;
 
        return 0;
}