Czynniki pierwsze

Z Wikipedii

Czynnik pierwszy danej liczby naturalnej złożonej, to dowolna liczba pierwsza, która dzieli tę liczbę.

Na przykład, jednym z czynników pierwszych liczby 20 jest 5.

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. Twierdzenie to nazywane jest często podstawowym twierdzeniem arytmetyki.

Przedstawienie danej liczby złożonej w postaci iloczynu czynników pierwszych nazywamy rozkładem liczby na czynniki pierwsze. Rozkład ten jest jednoznaczny w tym sensie, że każde dwa rozkłady danej liczby na czynniki pierwsze różnią się tylko kolejnością czynników.

Na przykład: 20 = 2·2·5 = 5·2·2 = 2·5·2 = 2²·5.

Kilka faktów o postaci czynników pierwszych:

każda liczba złożona ma czynnik pierwszy, który nie przekracza pierwiastka kwadratowego z tej liczby
każda liczba naturalna postaci 4k + 3 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy tej postaci
- 63 = 4·15 + 3 i 63 = 9·7, przy czym 7 = 4·1 + 3
każda liczba naturalna postaci 6k + 5 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy tej postaci
- 119 = 6·19 + 5 i 119 = 7·17, przy czym 17 = 6·2+5

Rozkład liczby naturalnej na czynniki pierwsze jest bardzo złożony obliczeniowo, co ma niebagatelne znaczenie dla kryptografii (patrz np. klucz RSA).

[edytuj] Rozkład liczby wymiernej na czynniki

Rozkład na czynniki pierwsze można też jednoznacznie wykonać dla dowolnej dodatniej liczby wymiernej $r$ . Wówczas:

$r=2^{w_2}\cdot 3^{w_3}\cdot 5^{w_5}\cdot 7^{w_7}\cdot \dots,$
gdzie $w p$ są liczbami całkowitymi.

Taki rozkład ma duże znaczenie w teorii liczb, w szczególności służy do konstrukcji liczb p-adycznych.

[edytuj] Algorytm rozkładu na czynniki pierwsze

Elementarnym sposobem rozkładu liczb na czynniki pierwsze jest kolejne dzielenie.

56|2
28|2
14|2
 7|7
 1|

Szukamy najmniejszej liczby pierwszej dzielącej daną liczbę (56). Jest to 2. Dzielimy: 56/2=28. Powtarzamy tę czynność dla kolejnych wyników aż do uzyskania w ilorazie liczby 1. Otrzymujemy wówczas wszystkie dzielniki pierwsze szukanej liczby. Na schemacie znajdują się one po prawej stronie.

[edytuj] Algorytm zaimplementowany w C++

/*
*Cel: Program służy do wypisywania kolejnych liczb pierwszych.
*/


#include<iostream>

using namespace std;

void fpierwsze(unsigned int tab[]); 

/******************************************************************************/
int main()
{
    cout <<"Witaj w programie rozbijajacym liczby na czyniki pierwsze. \n\n\n"; //Tytuł 
    //Deklaracja i przyjęcie zmiennych
    unsigned int x=0, y=0, z=0; //zmienne pomocnicze
    unsigned int tab[1000]; //wynik
    unsigned int a; //liczba przyjeta
    cout <<"Podaj liczbe, ktora chcesz rozbic na czynniki pierwsze:";
    cin  >>a;
    unsigned int pierwsze[15000];
    fpierwsze(pierwsze);
    
    //rozbicie na liczby pierwsze
    while(a>1)
    {
              if(a%pierwsze[x]==0)
              {
                                tab[y]=pierwsze[x];
                                a/=pierwsze[x];
                                x=0;
                                ++y;
                                
              }
              else
              {
                  ++x;
              }
    }
    
    //Wyświetlenie wyniku
    cout <<"\n\n\n";
    while(y)
    {
               cout <<tab[x] <<"\n";
               ++x;
               --y;
    }
    
    cout <<"\n\n\n\n\n\n\n\n\n\n";
    //zatrzymanie systemu
    system("PAUSE");
    return 0;
}
/******************************************************************************/
void fpierwsze(unsigned int tab[])
{
    //Deklaracja zmiennych
    int unsigned lim = 0; //numer kolejnej liczby pierwszej
    int unsigned sq = 4; //kwadrat liczby tab[lim]
    int unsigned i, j, f; //zmienne pomocnicze
    
    tab[0] = 2; //Wpisanie pierwszej liczby pierwszej
    
    //Obliczanie liczb pierwszych i wpisywanie ich do tablicy tab[n]
    for(i=3, j=1; j<15000; i+=2)
    {
             if(i>=sq)
             {
                      ++lim;
                      sq = tab[lim]*tab[lim];
             }
             for(f=1; f<lim; f++)
             {
                      if(i%tab[f]==0)
                      {
                                     break;
                      }
             }
             if(f>=lim)
             {
                       tab[j++]=i;
             }
    }
}