JustPaste.it

Liczby pierwsze - generacja liczb pierwszych

Do generacji liczb pierwszych wykorzystamy podaną w poprzednim rozdziale definicję liczby pierwszej. Algorytm będzie składał się z dwóch oddzielnych części. Pierwsza część bada, czy przekazana jej liczba jest liczbą pierwszą. Druga typuje liczby pierwsze, przekazuje je do zbadania pierwszej części i jeśli otrzyma pozytywną odpowiedź, wyprowadza je jako wynik. Takie podejście do rozwiązania problemu ułatwi nam wprowadzanie optymalizacji w następnych wersjach algorytmu.

7da0330914a7f8fbcd99abc8bca4ec02.gif

Funkcja Testuj ma za zadanie stwierdzenie, czy przekazana jej jako parametr liczba naturalna p jest liczbą pierwszą. Tego typu zadanie nazywa się badaniem pierwszości liczby (ang. primality testing).

2515e79f57cbac02bdec5e684b90b8fd.gif

Dane wejściowe

p - badana liczba przekazana do funkcji Testuj jako parametr, p f311ee417a4c9b690d3feda8f6312328.gif N

Dane wyjściowe

Wynik logiczny true, jeśli liczba p jest liczbą pierwszą lub wynik false w przypadku przeciwnym. Wynik stanowi wartość funkcji Testuj.

Zmienne pomocnicze

i - pełni rolę licznika pętli oraz kolejnych dzielników liczby p, i f311ee417a4c9b690d3feda8f6312328.gif N

445fb170af8079bdddbdfded170efe2b.gif

krok 1: Dla i = 2,3,...,p - 1 jeśli (p mod i) = 0, to Testuj(p) 3f1adeeee3bff7835db692b723200e20.gif false i zakończ algorytm
krok 2: Testuj(p) 3f1adeeee3bff7835db692b723200e20.gif true i zakończ algorytm

79d26d2e651e3a2284ddf7d65787ec49.gif

Na początku algorytmu inicjujemy pętlę kontrolowaną przez zmienną i, która początkowo przyjmuje wartość 2. Zmienna ta pełni również rolę kolejnych dzielników liczby p.

Pętla wykonuje się przy i mniejszym od p. W przeciwnym razie zostaje przerwana i algorytm kończy się zwrotem wartości logicznej true (prawda), co oznacza, iż żadna liczba z przedziału od 2 do p - 1 nie dzieli p. Zatem p jest liczbą pierwszą.

Wewnątrz pętli sprawdzamy, czy dzielnik i dzieli bez reszty liczbę p. Jeśli tak, to pętla również ulega przerwaniu i algorytm zwraca wartość logiczną false (fałsz) - liczba p nie jest pierwsza.

Jeśli reszta z dzielenia p przez i jest różna od 0, to zwiększamy i o 1 (bierzemy następny dzielnik) i wracamy na początek pętli.

Posiadając funkcję testującą pierwszość możemy utworzyć główny algorytm generacji liczb pierwszych. Algorytm ten będzie generował zadaną ilość początkowych liczb pierwszych.


34157bade6747899214053ed60c1b240.gif

Algorytm wykorzystuje poprzednio zdefiniowaną funkcję badania pierwszości liczby do generacji kolejnych liczb pierwszych.

2515e79f57cbac02bdec5e684b90b8fd.gif

Dane wejściowe

ile - określa ilość początkowych liczb pierwszych, które należy wygenerować, ile f311ee417a4c9b690d3feda8f6312328.gif N

Dane wyjściowe

Kolejno znalezione liczby pierwsze pi , i = 1,2,3,...,ile.

Zmienne pomocnicze

lp - zlicza znalezione liczby pierwsze, lp f311ee417a4c9b690d3feda8f6312328.gif N
p - zawiera kolejno testowane liczby, p f311ee417a4c9b690d3feda8f6312328.gif N, p = 2,3,...

445fb170af8079bdddbdfded170efe2b.gif

krok 1: Czytaj ile
krok 2: lp 3f1adeeee3bff7835db692b723200e20.gif 0p 3f1adeeee3bff7835db692b723200e20.gif 2
krok 3: Dopóki lp < ile wykonuj kroki 4...5. Inaczej zakończ algorytm.
krok 4:     Jeśli Testuj(p) = true, to wypisz p i zwiększ lp 3f1adeeee3bff7835db692b723200e20.gif lp + 1
krok 5:     Zwiększ p 3f1adeeee3bff7835db692b723200e20.gif p + 1 i  kontynuuj pętlę od kroku 3

79d26d2e651e3a2284ddf7d65787ec49.gif

 

Najpierw odczytujemy ile liczb pierwszych ma znaleźć nasz algorytm. Informacja ta zostanie umieszczona w zmiennej ile. Następnie inicjujemy licznik liczb pierwszych lp na 0 (nie znaleziono jeszcze żadnej liczby pierwszej) oraz p na 2 (pierwsza możliwa liczba pierwsza).

Teraz rozpoczyna się pętla warunkowa, która jest kontynuowana przy warunku lp < ile. Warunek ten będzie spełniony do momentu znalezienia zadanej ilości liczb pierwszych. Wtedy pętla zostanie przerwana i algorytm zakończy swoje działanie.

Wewnątrz pętli wywołujemy funkcję Testuj z parametrem p. Funkcja ta zbada, czy przekazany jej parametr jest liczbą pierwszą. Jeśli tak, to zwróci wartość logiczną true. W takim przypadku wypiszemy p i zwiększymy o 1 licznik lp. Jeśli p nie jest liczbą pierwszą, to funkcja Testuj zwróci wartość logiczną  false. Wtedy pominiemy wypisanie p i zwiększenie o 1 licznika lp.

Pętla zawsze kończy się zwiększeniem o 1 liczby p, czyli przejściem do kolejnej wartości, która potencjalnie może być liczbą pierwszą. Po tej operacji przechodzimy na początek pętli i cały opisany cykl rozpoczyna się od nowa.


c5bb14dda83739503c73fecb25c3f1ca.gif

3a267a34112e5283bf80fa61f5aaf04e.gif    
   
   

8212ff671fa543f51b55aebd584a2de3.gif

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       
Wydruk z uruchomionego programu
Generator zadanej ilości liczb pierwszych
-----------------------------------------
(C)2005 mgr Jerzy Wałaszek I LO Tarnów

Ile liczb wygenerować ? : 150

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 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541
547 557 563 569 571 577 587 593 599 601
607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733
739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863

KONIEC, naciśnij ENTER.
Microsoft Visual Basic 2005 Express Edition

 

Borland
Delphi 7.0
Personal
Edition
// Program generacji liczb pierwszych
// (C)2004 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-----------------------------------


program glp;

{$APPTYPE CONSOLE}

// Funkcja sprawdza, czy przekazana jako parametr
// liczba p jest liczbą pierwszą. Jeśli tak, to
// zwraca w wyniku true, przeciwnie zwraca false
//-----------------------------------------------

function Testuj(p : cardinal) : boolean;
var
i : cardinal;
begin
Testuj := true;
i := 2;
while i < p do
if
p mod i = 0 then
begin

Testuj := false; break;
end
else
i := i + 1;
end;

//----------------------------------
// Tutaj rozpoczynamy program główny
//----------------------------------

var
ile,lp,p : cardinal;

begin
writeln('Generator zadanej ilosci liczb pierwszych');
writeln('-----------------------------------------');
writeln('(C)2004 mgr Jerzy Walaszek I LO Tarnow');
writeln;
write('Ile liczb wygenerowac ? : '); readln(ile);
writeln;
lp := 0; p := 2;
while lp < ile do
begin
if
Testuj(p) then
begin

write(p : 8);
lp := lp + 1;
end;
p := p + 1;
end;
writeln;
write('Klawisz Enter = KONIEC'); readln; writeln;
end.
Borland
C++ Builder
6.0
Personal
Edition
// Program generacji liczb pierwszych
// (C)2004 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-----------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Funkcja sprawdza, czy przekazana jako parametr
// liczba p jest liczbą pierwszą. Jeśli tak, to
// zwraca w wyniku 1, przeciwnie zwraca 0
//-----------------------------------------------

bool Testuj(unsigned p)
{
unsigned i = 2;
while(i < p) if(!(p % i++)) return false;
return true;
}

//----------------------------------
// Tutaj rozpoczynamy program główny
//----------------------------------

main()
{
unsigned ile,lp,p;
char s[1];

cout << "Generator zadanej ilosci liczb pierwszych\n"
"-----------------------------------------\n"
"(C)2004 mgr Jerzy Walaszek I LO Tarnow\n\n"
"Ile liczb wygenerowac ? : "
;
cin >> ile;
cout << endl;
lp = 0; p = 2;
while(lp < ile)
{
if(Testuj(p))
{
cout << setw(8) << p; lp++;
}
p++;
}
cout << "\n\nKlawisz Enter = KONIEC";
cin.getline(s,1);
cin.getline(s,1);
}
Microsoft
Visual
Basic 2005
Express
Edition
' Program generacji liczb pierwszych
' (C)2005 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'-----------------------------------


Option Explicit On

Module Module1

' Funkcja sprawdza, czy przekazana jako parametr
' liczba p jest liczbą pierwszą. Jeśli tak, to
' zwraca w wyniku true, przeciwnie zwraca false
'-----------------------------------------------

Public Function Testuj(ByVal p As UInteger) As Boolean

Dim
i As UInteger

i = 2
While i < p
If (p Mod i) = 0 Then
Return
False
Else
i += 1
End If
End While
Return
True
End Function

Sub Main()

Dim ile, lp, p As UInteger

Console.WriteLine("Generator zadanej ilości liczb pierwszych")
Console.WriteLine("-----------------------------------------")
Console.WriteLine("(C)2005 mgr Jerzy Wałaszek I LO Tarnów")
Console.WriteLine()
Console.Write("Ile liczb wygenerować ? : ")
ile = Val(Console.ReadLine)
Console.WriteLine()
lp = 0 : p = 2
While lp < ile
If Testuj(p) Then
Console.Write("{0,8}", p)
lp += 1
End If
p += 1
End While
Console.WriteLine()
Console.WriteLine("KONIEC, naciśnij ENTER.")
Console.ReadLine()

End Sub

End Module
Python
# -*- coding: cp1250 -*-
# Program generacji liczb pierwszych
# (C)2005 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# im. K. Brodzińskiego
# w Tarnowie
#-----------------------------------

# Funkcja sprawdza, czy przekazana jako parametr
# liczba p jest liczbą pierwszą. Jeśli tak, to
# zwraca w wyniku 1, przeciwnie zwraca 0
#-----------------------------------------------

def Testuj(p):
for i in range(2, p):
if p % i == 0: return False
return True

#----------------------------------
# Tutaj rozpoczynamy program główny
#----------------------------------

print "Generator zadanej ilosci liczb pierwszych"
print "-----------------------------------------"
print "(C)2005 mgr Jerzy Walaszek I LO Tarnow"
print
ile = int(raw_input("Ile liczb wygenerowac ? : "))
print
lp, p = 0, 2
while lp < ile:
if Testuj(p):
print "%7d" % p,
lp += 1
p += 1
print
print

raw_input("Klawisz Enter = KONIEC")
JavaScript
<html>
<head>
</head>
<body>
<div
align="center">
<form
name="primes"
style="border: 1px outset #FF9933;
padding-left: 4px; padding-right: 4px;
padding-top: 1px; padding-bottom: 1px;
background-color: #FFCC66"
>
<h3 style=
"text-align: center">
Generator zadanej ilości liczb pierwszych
</h3>
<p style=
"text-align: center">
(C)2004 mgr Jerzy Wałaszek - I LO w Tarnowie
</p>
<hr>
<p style=
"text-align: center">
Ilość liczb pierwszych do wygenerowania
</p>
<p style=
"text-align: center">
<input type=
"text" name="T1" size="20" value="10">
</p>
<p style=
"text-align: center">
<input type=
"button" value="Generuj" name="B1" onclick="main()">
</p>
<p id=
"data_out" style="text-align: center">...</p>
</form>

<script language=javascript>


// Program generacji liczb pierwszych
// (C)2004 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-----------------------------------

// Funkcja sprawdza, czy przekazana jako parametr
// liczba p jest liczbą pierwszą. Jeśli tak, to
// zwraca w wyniku 1, przeciwnie zwraca 0
//-----------------------------------------------

function Testuj(p)
{
var i;

i = 2;
while(i < p) if(!(p % i++)) return 0;
return 1;
}

function main()
{
var s,ile,lp,p;

ile = parseInt(document.primes.T1.value);
if(isNaN(ile))
s = "<font color=Red><b>ZŁE DANE</b></font>";
else
{
lp = 0; p = 2; s = "";
while(lp < ile)
{
if(Testuj(p))
{
s += p + " "; lp++;
}
p++;
}
}
document.getElementById("data_out").innerHTML = s;
}

</script>

</div>
</body>
</html>


b2ef265f9a5c5d67ada5d7e81cbe73e0.gif

Dla celów badawczych zbierzemy dane o ilości wykonywanych operacji modulo. Wyposażymy program w odpowiedni licznik, którego stan będzie zwiększany każdorazowo przy wykonywaniu operacji modulo. Na końcu wyświetlimy stan licznika. Oto konieczne modyfikacje programu w Delphi:

Na początku programu dopisujemy deklarację zmiennej lom - licznika operacji modulo. Ponieważ liczba operacji modulo może przekraczać zakres typu cardinal (232 - 1), wybieramy rozszerzony typ zmiennoprzecinkowy extended, który daje dokładność około 19...20 cyfr znaczących.

// Program generacji liczb pierwszych
// (C)2004 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-----------------------------------

program glp;

{$APPTYPE CONSOLE}

var
lom : extended; // licznik operacji modulo

Druga zmiana polega na modyfikacji funkcji Testuj, aby w przy każdej operacji modulo następowało zwiększenie o 1 licznika lom.

// Funkcja sprawdza, czy przekazana jako parametr
// liczba p jest liczbą pierwszą. Jeśli tak, to
// zwraca w wyniku true, przeciwnie zwraca false
//-----------------------------------------------

function Testuj(p : cardinal) : boolean;
var
i : cardinal;
begin
Testuj := true;
i := 2;
while i < p do
begin

lom := lom + 1; // Tutaj jest zmiana
if p mod i = 0 then
begin

Testuj := false; break;
end
else

i := i + 1;
end;
end;

Trzecią zmianę wprowadzamy do programu głównego. Ma ona na celu zainicjowanie licznika lom na 0 przed rozpoczęciem zliczania operacji modulo oraz wyświetlenie jego stanu po wykonaniu zadania przez program.

//----------------------------------
// Tutaj rozpoczynamy program główny
//----------------------------------

var
ile,lp,p : cardinal;
begin
writeln('Generator zadanej ilosci liczb pierwszych');
writeln('-----------------------------------------');
writeln('(C)2004 mgr Jerzy Walaszek I LO Tarnow');
writeln;
write('Ile liczb wygenerowac ? : '); readln(ile);
writeln;
lp := 0; p := 2;
lom := 0; // Tutaj jest zmiana
while lp < ile do
begin
if
Testuj(p) then
begin

write(p : 8); lp := lp + 1;
end;
p := p + 1;
end;
writeln;
writeln('Liczba operacji modulo : ',lom:15:0);
// Tutaj jest zmiana
writeln;
write('Klawisz Enter = KONIEC'); readln; writeln;
end.

Wyniki uzyskane w tak zmodyfikowanym programie zebraliśmy w poniższej tabeli.

Wyniki badania ilości wykonanych operacji modulo
Ilość
l. pierw.
Ilość
op. modulo
Wzrost
10 134 -
100 24984 186,448
1000 3711627 148,560
10000 497007180 133,905
100000 62284747034 125,320

W pierwszej kolumnie znajduje się ilość generowanych przez program liczb pierwszych. Ilość ta w każdym wierszu tabeli wzrasta dziesięciokrotnie. Z uwagi na niską efektywność prezentowanego algorytmu zakończyliśmy na liczbie 100000. Wyznaczenie tej ilości liczb pierwszych zajęło naszemu komputerowi około 40 minut ciągłej pracy.

W drugiej kolumnie umieściliśmy ilość wykonanych przez program operacji modulo do wyznaczenia zadanej ilości liczb pierwszych.

W trzeciej kolumnie obliczyliśmy przyrost wykonanych operacji modulo w dwóch sąsiednich wierszach tabeli, np.:

24984 : 134 = 186,448
3711627 : 24984 = 148,560
497007180 : 3711627 = 133,905
, itd.

Przeanalizuj dane zawarte w powyższej tabeli i wyciągnij wnioski na temat klasy złożoności obliczeniowej prezentowanego w tym rozdziale algorytmu.




Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

 

Źródło: mgr Jerzy Wałaszek