Rozkład liczby naturalnej na czynniki pierwsze

Przykład 1

//*************************************************************************

//           PROGRAM ROZKLADA NA CZYNNIKI PIERWSZE WPROWADZONA LICZBE

//           Z KLAWIATURY ( WIEKSZA OD 1)

//               - wyznacza liczby pierwsze, ktorych iloczyn daje wartosc wprowadzonej liczby

//               - taki iloczyn jest tylko jeden jedyny

//*************************************************************************

// UWAGA: w petli for ustawiam ewentualne podzielniki a w petli while sprawdzam

// czy sa one czynnikami pierwszymi

// w petli for nie generuje liczb pierwszych tylko sprawdzam po kolei jak leci 2,3,4,5,itd

#include<iostream>

#include<cmath>           // dolaczam biblioteke <cmath>

                                          // bo w niej jest pierwiastek kwadratowy z liczby

using namespace std;

 int main()

 {               

     int a;   // zmienna na wczytana liczbe z klawiatury          

     int b;   // granica sprawdzania podzielnosci liczby 

     cin>>a;

     b=sqrt(a);      // zmienna b przyjmuje wartosc pierwiastka kwadratowego z

                            // wprowadzonej liczby.

// dlaczego tak przyjelam? dlaczego za granice sprawdzania podzielnosci wzielam

// pierwiastek kwadratowy z liczby wprowadzonej?

// bo wynika to z matematyki :-)

// czyli, jesli liczba jest liczba zlozona, to co najmniej jeden jej podzielnik 

// ma wartosc mniejsza lub rowna jej pierwiastkowi kwadratowemu 

// a reszta podzielnikow? tych większych od pierwiastka kwadratowego z liczby

// wprowadzonej? 

// będzie tylko taki jeden jedyny, o!!

// czy granica sprawdzania podzielnosci wprowadzanej liczby moze byc inna?

// tak, np. <a  lecz wtedy wykonujemy wiecej operacji 

// dla przypomnienia: jesli liczba jest liczba pierwsza, to jej czynnikiem pierwszym jest

// ona sama

    for (int i=2; i<=b; i++)     //  2 jest pierwsza liczba pierwsza, 

                                              // i<=b jest tu rownosc, bo sprawdzam wraz z wartoscia

                                              // pierwiastka kwadratowego z liczby bo np. 49 to 7^2       

    {

          while (a%i==0)          // dopoki wprowadzona liczba dzieli sie bez reszty przez i

                                              // czyli jej podzielnikiem jest i

            {

                cout<<i<<",";     // wypisz na ekranie wartosc podzielnika

                a=a/i;                  // tutaj najwazniejsza linika kodu czyli zmniejszam a,

                                            // zeby miec czynniki pierwsze a nie podzielniki

                                            // np. dla 8 zeby bylo 2,2,2, a nie 2,4,          

            }

       if ( a==1)                     // jesli wprowadzona liczba w wyniku operacji przypisania

                                           // ma wartosc 1, to mamy juz wszystkie podzielniki

      break;                          // i spokojnie mozemy przerwac petle for i caly program

                                           // tak bedzie np. dla 8, 12 ale już dla 17 nie   

    }

       if (a>1)                     // jesli wprowadzona liczba w wyniku operacji przypisania

                                        // ma wartosc wieksza od 1, to ta wartosc jest jej podzielnikiem

      cout<<a;                   // i wypisuje ten podzielnik

                                        // nasza  17  wlasnie sie lapie w tej opcji

// lapie sie tez podzielnik 3 liczby 6, ktory jest wiekszy od pierwiastka kwadratowego z 6

    cin.get();

    cin.ignore();

    return 0;

 }