BartoIT Blog

O informatyce, po swojemu, inaczej

Rozkład liczby na czynniki pierwsze

Na stronie Centralnej Komisji Egzaminacyjnej ( CKE ) możemy znaleźć wykaz algorytmów, których znajomość jest wymagana. Ostatnio pisałem na temat algorytmu, który sprawdza, czy dana liczba jest liczbą pierwszą. Wpis postanowiłem udostępnić na wykop.pl i zauważyłem, że wywołał on dyskusję, mimo że nie wypadł pozytywnie pod kątem ocen ( 3x wykop / 8x zakop ) ale akurat to mało istotne. Dziś poruszę kolejny algorytm jakim jest umiejętność rozkładu danej liczby na czynniki pierwsze.

Przestrzegam, aby uniknąć specyficznych komentarzy …

Algorytm został przygotowany na liczby, przy których komputer się nie napoci- jeżeli jesteś naprawdę dobry w te klocki pozostaw w komentarzu swoją opinię ale oprócz tego lepszy, bądź ciekawszy sposób rozwiązania, który będzie dobry dla komputera przy obliczaniu nawet 3^758930-2.

Zaczynając od teorii …

Czynnik pierwszy liczby naturalnej, to dowolna liczba pierwsza, która dzieli tę liczbę.
„Jedna z podstawowych obserwacji dotyczących liczb naturalnych mówi, że każda liczba naturalna większa od 1 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy. Wynika stąd dalej, że każda liczba naturalna większa od 1 jest pierwsza, lub daje się zapisać w postaci iloczynu liczb pierwszych.

 

Rozkład liczby naturalnej na czynniki pierwsze jest bardzo złożony obliczeniowo, co stanowi podstawę kryptografii asymetrycznej (patrz np. klucz RSA).”

~ Wikipedia.pl
Jak widzę, to kolejny już dosyć złożony obliczeniowo algorytm- no cóż, mówi się trudno.
Rozwiązanie
Schemat krokowy
1.Podaj liczbę naturalną n.
2.Jeżeli n>1 wtedy
zmienna pomocnicza i=1
dopóki i<=pierwiastek kwadratowy z n
dopóki !(n mod i)
wypisz „i * ”
jeżeli n=1 przerwij, a i zwiększ o 1
w przeciwnym wypadku
wypisz „niewłaściwe dane” i zakończ algorytm
Algorytm w C++

 

#include <iostream>
#include <math.h>
#include <stdlib.h>

using namespace std;


int main(int argc, char *argv[])
{
  unsigned long n; 

   cout << "Rozklad liczby naturalnej na czynniki pierwszen"
        "Podaj n = ";

   cin >> n; cout << endl;

   if (n > 1) 
   {
     cout << n << " = ";

     int i = 2; 

      while (i <= (unsigned long)sqrt((double)n))
      {

      while (!(n % i))
       {
       n /= i; 
       cout << i << " x ";
       }

       if (n == 1) break;
       i  ;
      }

     if (n > 1) cout << n;

   }
   else cout << "Niewlasciwe danen"; 

   cout << endl << endl;
 system("PAUSE");
 return 0;
}

More Posts