Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

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:

{tex}24=2\cdot 2\cdot 2 \cdot 3{/tex}

{tex}100=2\cdot 2\cdot 5 \cdot 5{/tex}

{tex}1520=2\cdot 2\cdot 2 \cdot 2 \cdot 5 \cdot 19{/tex}

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 się dzieli to wypisujemy {tex}2{/tex} i skracamy naszą liczbę przez {tex}2{/tex}. Czynność powtarzamy tak długo, jak długo liczba {tex}n{/tex} jest podzielna przez {tex}2{/tex}. 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 {tex}1{/tex}.

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>
#include<cstdlib>
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;
        }
 
        system("pause");
        return 0;
}
 

 

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

#include<iostream>
#include<cstdlib>
#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;
 
        system("pause");
        return 0;
}