Primzahlen bis 30 ohne dividieren herausfinden?
Das muss ich unbedingt herausfinden. Habe auch nach langem Suchen keinen Lösungsansatz gefunden.
7 Antworten
mach ne boolean Liste "kann Prim sein"=true von 2 bis 30 und eine Liste von "bisher gefundenen Primzahlen"=leer und mache damit folgendes:
nehme die kleinste Zahl, die Prim sein kann, aber noch nicht in "bisher gefundenen Primzahlen" drin ist, multipliziere sie auf jede denkbare Weise mit den Zahlen, die in "bisher gefundenen Primzahlen" drin sind und sich selbst (ohne über 30 zu kommen) und setze alle Zahlen, die dabei raus kommen bei "kann Prim sein" auf false.
Kurz gesagt: eliminiere einfach alle Zahlen, die mittels Multiplikation KEINE Primzahlen sind.
Du könntest ein Sieb des Eratosthenes durchführen.
https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
Schreibe die Zahlen von 2 bis 30 in eine Liste.
Die kleinste noch nicht verwendete Zahl ist 2. Diese ist also eine Primzahl.
(2² = 4 < 30)
Streiche alle Vielfachen von 2 (außer der 2 selbst) aus der Liste.
Die kleinste noch nicht verwendete Zahl ist 3. Diese ist also eine Primzahl.
(3² = 9 < 30)
Streiche alle Vielfachen von 3 (außer der 3 selbst) aus der Liste.
Die kleinste noch nicht verwendete Zahl ist 5. Diese ist also eine Primzahl.
(5² = 25 < 30)
Streiche alle Vielfachen von 5 (außer der 5 selbst) aus der Liste.
Die kleinste noch nicht verwendete Zahl ist 7. Diese ist also eine Primzahl.
(7² = 49 > 30)
Wegen 7² > 30 sind auch die restlichen noch nicht gestrichenen Zahlen Primzahlen.
Demnach erhält man für die Primzahlen bis 30:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Du kannst auch einfach multiplizieren.
Bis 30 ist das relativ einfach. Es gibt ja Zahlen, da weiß man einfach, dass 3*3=9 ist, 3*5=15 usw. Die zahlen kannst du also automatisch ausschließen.
Schreibe alle Zahlen unter 30 auf, die keine Vielfachen von 2, 3 oder 5 sind.
Schaffst du!
Dafür brauchst du keinen Computer. Das 1x3 reicht. Vielfache von 2 und 5 erkennt man an der letzten Ziffer.
Du brauchst nicht einmal das 1x3. Wenn beide Ziffern zusammen 3 oder 9 ergeben, schreibst du die Zahl nicht auf. (6, 15 und 24 sind schon wegen der letzten Ziffer raus)
schau dir mal als Lösungsansatz das Sieb des Eratosthenes an, als Prinzip und als Pacal-Implementierung.