Liczba najbliżej średniej

 Program wyznaczający spośród podanych liczb te które znajdują się najbliżej średniej.

 

               Sito Eratostenesa

Zbiór liczb naturalnych bez liczby 1 składa się z dwóch rodzajów liczb:

1. Liczb złożonych, które są podzielne przez liczby mniejsze z tego zbioru.

2. Liczb pierwszych, które nie są podzielne przez liczby mniejsze z tego zbioru.

Pierwszy rodzaj liczby to wielokrotności liczb mniejszych. Jeśli zatem ze zbioru usuniemy wielokrotności kolejnych liczb, to pozostaną w nim tylko liczby pierwsze. Na tej właśnie zasadzie działa sito Eratostenesa - przesiewa liczby wyrzucając ze zbioru ich kolejne wielokrotności.

Algorytm Sita Eratostenesa

Wejście:

    n  - określa górny kraniec przedziału <2,n>, w którym poszukujemy liczb pierwszych
Wyjście:

    Liczby pierwsze z przedziału <2,n>

Dane pomocnicze:

    T[ ] - tablica o elementach logicznych, których indeksy obejmują przedział <2,n>

    i  - kolejne liczby, których wielokrotności usuwamy
    w  - wielokrotności liczb i
 

Krok 1:	Ustaw wszystkie elementy T[ ] na true
Krok 2:	i  ← 2	; rozpoczynamy od liczby 2
Krok 3:	Jeśli i  ≥ n, to idź do kroku 11	; sprawdzamy, czy liczby osiągnęły koniec przedziału <2,n>
Krok 4:	w  ← i  + i	; liczymy pierwszą wielokrotność liczby i
Krok 5:	Jeśli w  > n, to idź do kroku 9	; sprawdzamy, czy wielokrotność wpada w przedział <2,n>
Krok 6:	T[w] ← false	; jeśli tak, to usuwamy ją ze zbioru liczb
Krok 7:	w  ← w  + i	; obliczamy następną wielokrotność
Krok 8:	Idź do kroku 5	; i kontynuujemy usuwanie wielokrotności
Krok 9:	i  ← i  + 1	; wyznaczamy następną liczbę
Krok 10:	Idź do kroku 3	; i kontynuujemy
Krok 11:	i  ← 2	; przeglądamy tablicę T[ ]
Krok 12:	Jeśli i  > n. to zakończ
Krok 13:	Jeśli T[i] = true, to pisz i	; wyprowadzamy liczby, które pozostały w T[ ]
Krok 14:	i  ← i  + 1
Krok 15:	Idź do kroku 12

 

#include <iostream>

using namespace std;

const unsigned N = 1000;  // definiuje koniec przedziału <2,N>

int main()
{
    bool T[N+1];  // tablica musi obejmować indeksy od 2 do N
    unsigned i,w;

    // ustawiamy wszystkie elementy T[] na true

    for(i = 2; i <= N; i++) T[i] = true;

    // eliminujemy w T[] wielokrotności

    for(i = 2; i < N; i++)
        for(w = i + i; w <= N; w += i) T[w] = false;

    // wyświetlamy indeksy elementów pozostawionych w T[]

    for(i = 2; i <= N; i++)
        if(T[i]) cout << i << " ";

    cout << endl << "--- KONIEC ---\n\n";

    return 0;
} 

Wyznaczanie liczb pierwszych

 

Generacja liczb pierwszych

Liczba pierwsza jest liczbą naturalną, która posiada dokładnie dwa różne podzielniki - 1 i siebie samą.

Liczba 1 nie jest pierwszą, ponieważ dzieli się tylko przez 1, a nie posiada drugiego podzielnika różnego od 1. Przykłady liczb pierwszych:

 

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ...

 

Liczby pierwsze maja olbrzymie zastosowanie we współczesnej informatyce. Na nich opierają się zaawansowane systemy szyfrujące, używane przez banki, służby państwowe i wojsko. Dlatego umiejętność sprawdzania pierwszości liczby oraz generacji liczb pierwszych jest podstawową umiejętnością każdego informatyka.

WYZNACZANIE LICZB PIERWSZYCH SPOSOBEM KLASYCZNYM

Dowód Euklidesa na nieskończoność zbioru liczb pierwszych:

Zbiór liczb pierwszych jest zbiorem nieskończonym. Oznacza to, że dla dowolnie dużej liczby naturalnej zawsze znajdziemy liczbę pierwszą, która jest od niej większa. Nieskończoność tego zbioru udowodnił grecki matematyk Euklides. Zastosował on dowód przez sprowadzenie do sprzeczności.

Załóżmy, że zbiór liczb pierwszych P  jest zbiorem skończonym i zawiera n  różnych liczb pierwszych:

 

 

Euklides tworzy liczbę E (liczbę Euklidesa) wg następującego wzoru:

 

 

Liczby E  nie dzieli żadna z liczb należących do zbioru P  - zawsze zostanie reszta 1:

 

 

1. Liczba E  nie jest podzielna przez żadną z liczb różną od 1 i siebie samej - zatem jest nową liczbą pierwszą, której nie ma w zbiorze P.

2. Liczba E  jest podzielna przez liczbę pierwszą, której nie ma w zbiorze P, ponieważ te liczby E  nie dzielą.

Trzeciej możliwości nie ma. W obu możliwych przypadkach dostajemy nową liczbę pierwszą, której zbiór P  nie zawiera. Przeczy to założeniu, że zbiór P  zawierał wszystkie liczby pierwsze. Skoro tak, zbiór liczb pierwszych nie może być zbiorem skończonym.

Algorytm sprawdzania, czy liczba p jest liczbą pierwszą

Wejście:

p  - sprawdzana liczba naturalna

Wyjście:

t  = true, liczba p  jest liczbą pierwszą
t  = false, liczba p  nie jest liczbą pierwszą

Zmienne pomocnicze:

i  - kolejne dzielniki naturalne dla liczby p

Krok 1: t ← true                       ; zakładamy sukces

Krok 2: i ← 2                           ; pierwszy dzielnik

Krok 3: Jeśli i ≥ p, to zakończ ; sprawdzamy, czy dzielnik wciąż jest w zakresie od 2 do p-1

Krok 4: Jeśli p nie dzieli się przez i, to idź do kroku 7 ; przechodzimy do wyznaczenia                                                                                                 kolejnego podzielnika

Krok 5: t ← false                      ; p jest podzielne, zatem nie jest pierwsze

Krok 6: Zakończ

Krok 7: i ← i + 1                      ; wyznaczamy kolejny dzielnik

Krok 8: Idź do kroku 3             ; kontynuujemy sprawdzanie podzielności
  

 

Program wykorzystujący podany algorytm do generacji n  liczb pierwszych.

#include <iostream>

using namespace std;

int main()
{
    int n,i,p,lp;
    bool t;

    cin >> n;

    lp = 0;
    p = 2;
    
    while(lp < n)
    {
        t = true;
        for(i = 2; i < p; i++)
            if(p % i == 0)
            {
                t = false;
                break;
            }

        if(t)
        {
            cout << p << " ";
            lp++;
        }
        p++;
    }

    cout << endl;

    return 0;
} 

30 tysięcy wyrazów w 35.828sekund. Jest wolniejszy o 
22.399 sekund od ulepszonej wersji.

Ulepszenie algorytmu generacji liczb pierwszych przez sprawdzanie podzielności
Jeśli liczba p  jest liczbą złożoną (a zatem nie jest liczbą pierwszą), to można ją zapisać w postaci iloczynu dwóch liczb naturalnych a  i b, które obie są różne od liczby p:
 
 
Z tych dwóch liczb a  i b  wystarczy znaleźć tylko jedną, aby wykluczyć pierwszość liczby p. Mamy dwa możliwe przypadki:
Oba dzielniki są równe:
Oba dzielniki są różne:

Algorytm sprawdzania, czy liczba p jest liczbą pierwszą - wersja ulepszona
Wejście:
p  - sprawdzana liczba naturalna, p  > 2
Wyjście:
t  = true, liczba p  jest liczbą pierwszą
t  = false, liczba p  nie jest liczbą pierwszą
Zmienne pomocnicze:
g  - pierwiastek całkowity z p
i  - kolejne dzielniki nieparzyste dla liczby p

Krok 1: t ← true  ; zakładamy sukces
Krok 2: Jeśli p  dzieli 2, to idź do kroku 7 ; eliminujemy
                                             liczby podzielne przez 2

Krok 3: g ← |√p|              ; obliczamy pierwiastek całkowity z p
Krok 4: i ← 3                     ; pierwszy dzielnik nieparzysty
Krok 5: Jeśli i > g, to zakończ ; sprawdzamy, czy dzielnik wciąż jest
                                                       w zakresie od 2 do pierwiastka z p

Krok 6: Jeśli p nie dzieli się przez i, idź do kroku 9 ; przechodzimy do
                                                          wyznaczenia następnego podzielnika

Krok 7: t ← false              ; p jest podzielne, zatem nie jest pierwsze
Krok 8: Zakończ  
Krok 9: i ← i + 2              ; wyznaczamy kolejny dzielnik nieparzysty 
Krok 10: Idź do kroku 4 ; kontynuujemy sprawdzanie podzielności
PROGRAM:
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n,i,p,lp,g;
    bool t;

    cin >> n;

    lp = 0;
    p = 2;
    
    while(lp < n)
    {
        t = true;
        if(p > 2)
        {
            if(p % 2)
            {
                g = sqrt(p);
                for(i = 3; i <= g; i += 2)
                    if(p % i == 0)
                    {
                        t = false;
                        break;
                    }
            }
            else t = false;
        }

        if(t)
        {
            cout << p << " ";
            lp++;
        }
        p++;
    }

    cout << endl;

    return 0;
} 

30tysięcy wyrazów w 13.429sekund. Jest o 22.399sekund
szybszy od zwykłego algorytmu.

 NWD I NWW

Program, który za pomocą metody odejmowania algorytmu Euklidesa oblicza: 

NWD- Największy wspólny dzielnik dwóch liczb całkowitych.
NWW- Najmniejsza wspólna wielokrotność liczb naturalnych