Ich versuchs mal! Primzahlen!

Moin Moin,

ich hab ein Problem mit einer Programmieraufgabe. So wie ich das sehe habt Ihr das ziemlich drauf mit Programmieren und mein Prof meinte, diese Aufgaben kann man in 5 Minuten erledigen, naja, ich jedenfalls nicht.

Es soll ein Programm sein, das mir entweder sagt, ob die eingegebene Zahl eine Primzahl ist, oder es gibt mir alle Primzahlen in einem vorgegebenen Bereich aus.

Ich hab schon mal das Gerüst gebaut, aber weiter weiß ich nicht. Das Programm soll in dem Rahmen laufen. Im unteren Fenster sollen immer die Hilfsanweisungen in der ersten Zeile stehen. Wenn man z drückt kann man in der zweiten Zeile eine beliebige Zahl angeben, mit Enter bestätigen und in großen Hauptfenster steht dann “xyz ist eine Primzahl” oder eben auch nicht. Wenn man b drückt, soll man einen Bereich angeben können und alle Primzahlen in diesem Bereich erscheinen dann in tabellenform im Hauptfenster.
Wenn man h drückt, soll dieser Hilfstext erscheinen:
Programm zur Berchnung von Primzahlen

Primzahlen sind durch 1 und durch sich selbst teilbar!

Wollen Sie prüfen lassen, ob eine Zahl eine Primzahl ist,
dann drücken Sie “Z” und geben eine beliebige Zahl ein.
Bestätigen Sie mit “Enter” und das Ergebnis erscheint auf
dem Bildschirm.
Wollen Sie alle Primzahlen angezeigt bekommen die in einem
bestimmten Bereich sind, dann drücken Sie “B” und geben den
Bereich ein aus dem die Primzahlen angezeigt werden sollen
(z.B. x 50 bis y 500).
Zum Löschen des Bildschirms drücken Sie “L”

Es wäre toll, wenn Ihr mir helfen könntet.


uses crt;

const ESC = #27;
      FKT = #0;                
      F1  = #59;               
      F2  = #60;
      F3  = #61;

var eingabe: char;
    i,y : integer;


<
<
<
     PROZEDUREN????
>
>
>





begin
  clrscr;

  write ('╔');                               {alt 201}
  for i := 1 to 78 do write ('═');           {alt 205}
  write ('╗');                               {alt 187}
  for i := 2 to 45 do
    begin
      gotoxy(y*1+80,i);
      write ('║');                           {alt 186}
      gotoxy(y*79+1,i);
      write ('║');                           {alt 186}
    end;
  gotoxy (1,46);
  write('╚');                                {alt 200}
  for i := 1 to 78 do write ('═');           {alt 205}
  write ('╝');                               {alt 188}

  gotoxy (1,43);
  write('╠');                                {alt 204}
  for i := 1 to 78 do write ('═');           {alt 205}
  write ('╣');                               {alt 185}

  gotoxy (1,3);
  write('╠');                                {alt 204}
  for i := 1 to 78 do write ('═');           {alt 205}
  write ('╣');                               {alt 185}

  gotoxy(2,2);
  write('NAME');

  gotoxy(35,2);
  write('Übung 5');

  gotoxy(74,2);
  write('2007');

  window(2,44,77,45);

  gotoxy(2,44);
  write('h = Hilfstext, z = Primzahl, b = Bereich, ESC = Ende');



  clrscr;                         
  repeat
    eingabe := upcase(readkey);   
    case eingabe of               
      FKT : begin
              eingabe:=readkey;   
              case eingabe of
                F1:;
                F2:;
                F3:;
                else writeln('falsche Funktionstaste CODE',ord(eingabe));
              end;
            end;
      'A' : write('Das ist eine Primzahl');         {Zahl eingeben}
      'B' : write(eingabe);                         {Bereich von x bis Y}
      'L' : clrscr;
      else writeln(eingabe,' ',ord(eingabe));
    end;
  until eingabe = ESC;
end.



ein algorithmus, der testet, ob eine gegebene zahl eine primzahl ist oder nicht, nennt man einen primzahltest. da gibt es mehrere algorithmen mit unterschiedlichen zahlentheoretischen grundlagen. es stellt sich also die frage, welchen algorithmus willst du programmieren, in welcher grössenordnung liegen die zahlen.

zur theorie: schau mal in die wikipedia
zur praxox: auf primzahlen.zeta24.com gibt es einen online test und den quellcode für den miller rabin test.

Die einfachste (und ineffizienteste Lösung) besteht darin, die eingegebene Zahl durch jede kleinere Zahl per modulo-operation zu teilen. Ist der Rest 0, dann ist die Zahl keine Primzahl, denn sie ist durch eine andere Zahl (die ungleich 1 und der zu prüfenden Zahl selbst) teilbar ist. Dieses Verfahren kann man noch an vielen Stellen verbessern, aber das kannst du ja selbst herausfinden.