    
THOMAS
Unregistrierter Gast
| | Veröffentlicht am Montag, den 29. April, 2002 - 20:36: | 
|
tag ihr alle..
Mit PRIM bezeichnet man das problem , zu entscheiden , ob eine binär kodierte natürliche Zahl n eine Primzahl ist oder nicht.
Betrachten sie folgenden Algorithmus:
Input : n
Überprüfe für alle natürlichen Zahlen i mit 2³ i £ Ön, ob die Zahl n durch i teilbar ist.
Falls dies in keinem Fall zutrifft, ist n eine Primzahl ; sonst nicht.
a) Arbeitet dieser Algoritmus korrekt ?
b) Arbeitet dieser Algorithmus polynomiell ?
Beweisen sie ihre Antworten.
Vielleicht hat jemand ein paar Ideen dazu....Thomas |
