Turbo Pascal Primzahlen

S

sphinx3k1

Hi Programmier-Leutz!!
Ich hab hier ne Aufgabe mit der ich in TP nicht fertig werde...bitte helft mir:

Es sollen alle Primzahlen bis 1000 ermittelt werden.
Hier gibt es einige Strategien zur Optimierung des Programs. Zunächst wird die entsprechende Zahl durch 2,3,4,5... geteilt um die Teilbarkeit zu testen. Die erste Optimierung liegt sofort auf der Hand.

Interessant wird es wenn man sich überlegt, dass man zB die Teilbarkeit durch 9 nicht mehr testen muss, weil die Zahl dann vorher durch 3 teilbar gewesen wäre.

[Fortgeschrittene](stand so aufm Blatt) können an dieser Stelle einmal die Wirkung ihrer Optimierung testen, indem sie den Computer die Zeit zur Berechnung stoppen lassen ( gettime / unit windos ) Außerdem wird man auf einen neuen Variablentyp stoßen.

Bitte helft mir...*heul*
THX
http://www.third-level-design.de
 
ich hab das auch mal programmiert und ich glaub ich kann mich da an ein paar sachen noch erinnern:

erstens mal: alle primzahle sind darstellbar durch 6*n + 1 oder 6*n - 1.
also muss man nicht alle zahlen von 1 bis ende (z.b. 1000) testen, sondern nur die, die 1 oder 5 modulo 6 sind, d.h. deren rest bei einer teilung durch 6 5 oder 1 ist....

zweitens schreibt man sich ja die gefundenen prinzahlen in einen array.... den aknn man ja verwenden, um nur die teilbarkeit durch die kleineren prinzahlen zu testen, man muss also nicht durch alle kleineren zahlen teilen, somi würd edie 9 als nicht-prinmzahl also gar nicht in frage kommen :)

und drittens muss man immer nur die zahler die <= der wurzel aus der aktuellen zahl sind testen, da eine zahl, die größer als die ihre wurzel ist, niemals deren teiler sein kann.....

logisch oder????? najais eigendlich alles nur mathe....aber die umsetztung in jeder programmiersprache is ganz einfach....da hab ich jetzt aber keine lust dazu:)

//bad taste
 
"Alle Primzahlen sind darstellbar durch 6*n+1 oder 6*n-1."
Falsch, denn 2 und 3 sind auch Primzahlen, und für 6*n+1=2 und 6*n-1=3 gibt es keine n im Bereich der natürlichen Zahlen. Und ein Gegenbeispiel bringt einen Satz bekanntlich zu Fall, womit dieser falsch ist :p
 
also herr besserwisser:):
spass....

der komplette satz lautet....

außer den primzahlen 2 und 3 sind alle primzahlen
von der form 3n + 1 oder 3n - 1,
von der form 4n + 1 oder 4n - 1,
von der from 6n + 1 oder 6n - 1.

das ist allgemein und lässt sich auch zusammenfassen als 6n +/- 1

da muss man mal kurz drüber nach denken....

und dass mit dem alle primzahlen außer 2 und 3, naja fand ich net erwähnenswert, weil das nun mal logisch ist........

(vergleiche skript zur vorbereitung zur deutschen mathematik-olympiade 1998:))

also is das weder ein widerspruch noch sonst irgendwas..das is einer der grundlegenden und nützlichsten sätze der zahlentheorie:)

//bad taste
 
Zuletzt bearbeitet:
ja gut.....im endeffekt is es ja dasselbe, ob man alle zahlen auf die teilbarkeit durch die kleineren primzahlen testet, oder man die vielfachen der primzahlen rausschmeist....

aber es geht natürlich etwas schneller....ich fand nur, dass das andere schneller zu peilen is und einfach kürzer zu beschreiben war:)

//bad taste
 
Zurück