Gymnasium Kamenz/Informatik/Verschlüsselung

Wiki-Quelltext dieser Seite.

<language>Pascal</language>
[[Bild:InfWolfS_Verschlüsselung.gif|InfWolfS_Verschlüsselung.gif]]
== Das Sieb des Eratosthenes ==

Der griechische Mathematiker, Geograph, Philosoph, Philologe und Dichter '''Eratosthenes von Kyrene''' (* zwischen 276 und 273 v. Chr.; † um 194 v. Chr.) war der erste Gelehrte der Antike, der durch eine wissenschaftlich fundierte Messung den Umfang der Erde mit erstaunlicher Genauigkeit bestimmt hat.<br />
Auf ihn geht aber auch ein interessanter Algorithmus zur Bestimmung aller ''Primzahlen'' zurück.<br />

=== Algorithmus ===

* Notiere die natürlichen Zahlen, beginne mit <math>2</math>.

<blockquote>
<math>2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...</math>
</blockquote>

* Unterstreiche die <math>2</math> und streiche alle Vielfachen von <math>2</math>.

<blockquote>
<math>\usepackage{ulem} \uline{2}, 3, \xout{4}, 5, \xout{6}, 7, \xout{8}, 9, \xout{10}, 11, \xout{12}, 13, \xout{14}, 15, \xout{16}, 17, \xout{18}, 19, \xout{20}, ...</math>
</blockquote>

* Unterstreiche die erste freie Zahl (in diesem Falle die Zahl <math>3</math>) und streiche deren Vielfachen.

<blockquote>
<math>\usepackage{ulem} \uline{2}, \uline{3}, \xout{4}, 5, \xout{6}, 7, \xout{8}, \xout{9}, \xout{10}, 11, \xout{12}, 13,
\xout{14}, \xout{15}, \xout{16}, 17, \xout{18}, 19, \xout{20}, ...</math>
</blockquote>

* Verfahre mit allen weiteren freien Zahlen ebenso.

<blockquote>
<math>\usepackage{ulem} \uline{2}, \uline{3}, \xout{4}, \uline{5}, \xout{6}, \uline{7}, \xout{8}, \xout{9}, \xout{10}, \uline{11}, \xout{12}, \uline{13}, \xout{14}, \xout{15}, \xout{16}, \uline{17}, \xout{18}, \uline{19}, \xout{20}, ...</math>
</blockquote>

* Alle unterstrichenen Zahlen sind Primzahlen.

=== Lösungsidee ===

* Belege ein eindimensionales Feld (''Array'') mit <math>n</math> ganzen Zahlen. Beginne mit der <math>2</math>.
* Setze die Vielfachen jedes der von Null verschiedenen Feldelemente auf Null. Beginne ebenfalls bei <math>2</math>.
* Gib nur die Feldelemente aus, die von Null verschieden sind.

<language>Pascal</language>
=== Implementation ===

<code id="4d35b3f554587">
var grenze: integer;
    liste : array[0..1000000] of integer;
procedure primausgabe(n: integer);
 var i, zaehler: integer;
 begin
  zaehler:=0; 
  for i:=2 to n do
   if liste[i]<>0 then
   begin
    zaehler:=zaehler+1; 
    if (zaehler mod 15)=0 then
     writeln(inttostr(liste[i])+', ')
    else
     write(inttostr(liste[i])+', ');
   end;
 end;

procedure primsieb(n: integer);
 var i, j: integer;
 begin 
  // Implementation des Algorithmus
 end;
</code>

<code id="4d35b3f554606" hidden>
var testliste: array[0..1000000] of integer;

procedure testprimsieb(n: integer);
 var i, j: integer;
 begin 
  for i:=2 to n do testliste[i]:=i;
  for i:=2 to n do
  begin
   j:=2*i;
   while j<=n do
   begin
    testliste[j]:=0;
    j:=j+i;
   end;
  end;
 end;

function korrekt(n: integer): boolean;
 var i   : integer;
     test: boolean;
 begin
  test:=true;
  primsieb(n);testprimsieb(n);
  for i:=2 to n do 
   test:=test and (testliste[i]=liste[i]);
  result:=test;
 end;
</code>

<check>
result:=korrekt(20);
</check>

<run id="4d2cc6e0afa01">
grenze:=1000;
primsieb(grenze);
primausgabe(grenze);
</run>


<code id="4d36ea285fa00">
var z1, z2, s, d, p: integer;
begin
 s:= z1+z2;
 d:= z1-z2;
 p:= z1*z2;
end;
</code>

<run id="4d36ea285fa90">
z1:=7;
z2:=5;
</run>

=== Aufgaben ===

# Diskutieren Sie ausführlich, ob sich der intuitive Algorithmusbegriff auf das "Sieb des Eratosthenes" anwenden lässt.
# Untersuchen Sie die Effizienz Ihrer Implementation.