Programm um Primzahlen herauszufinden

Übersicht

BlitzBasic

Beginners-Corner

	Mastakiller Betreff: Programm um Primzahlen herauszufinden	Mo, Feb 07, 2005 23:25 Antworten mit Zitat
Hiho kann mir einer helfen ?? Wir machen Blitzbasic in der Schule und sollen ein Program schreiben mit dem man alle Primzahlen herrausfindet und ich hab keine Ahnung weil wir erst mit dem Programm angefangen haben. Wenn mir einer helfen kann dann soll er sich doch bidde melden. thx

Mastakiller

Betreff: Programm um Primzahlen herauszufinden

Mo, Feb 07, 2005 23:25
Antworten mit Zitat

Hiho kann mir einer helfen ?? Wir machen Blitzbasic in der Schule und sollen ein Program schreiben mit dem man alle Primzahlen herrausfindet und ich hab keine Ahnung weil wir erst mit dem Programm angefangen haben. Wenn mir einer helfen kann dann soll er sich doch bidde melden.

thx

	NetPad	Mo, Feb 07, 2005 23:33 Antworten mit Zitat
hier ist natürlich die frage, wie hoch du gehen willst. nehmen wir einmal an, du möchtest alles primzahlen bis 1000. also erstes machst du ein array, das entweder primzahl(true), oder keine primzahl ist(false) und 1000 werte annehmen kann. nun klapperst du die zahlen ab: 1 --> true 2 --> true ;hier beginnt das gescheite! 22 --> false 23 -->false 24 --->false das geht dann so weiter, bis 2x 1000 erreicht. dann erhöst du 2 um 1( =3 ). dann schaust du, ob im array 3 bereits true oder false gesetzt wurde, wenn nicht -->true dann wieder alle vielfachen von 3 abklappern: 32 -->false 33 -->false ... ... ... grs NP

NetPad

Mo, Feb 07, 2005 23:33
Antworten mit Zitat

hier ist natürlich die frage, wie hoch du gehen willst. nehmen wir einmal an, du möchtest alles primzahlen bis 1000.

also erstes machst du ein array, das entweder primzahl(true), oder keine primzahl ist(false) und 1000 werte annehmen kann. nun klapperst du die zahlen ab:
1 --> true
2 --> true ;hier beginnt das gescheite! Very Happy

2*2 --> false
2*3 -->false
2*4 --->false

das geht dann so weiter, bis 2*x 1000 erreicht. dann erhöst du 2 um 1( =3 Laughing

). dann schaust du, ob im array 3 bereits true oder false gesetzt wurde, wenn nicht -->true
dann wieder alle vielfachen von 3 abklappern:
3*2 -->false
3*3 -->false
...
...
...

grs NP

	wunderkind	Mo, Feb 07, 2005 23:50 Antworten mit Zitat
Testen ist die einzige Möglichkeit. Es gibt (meines Wissen) schlicht keine einfache Funktion die z.B. alle Primzahlen zwischen x und y errechnet. Zum Testen aber, ob eine Zahl eine Primzahl ist oder nicht, gibt es mehrere Verfahren.

wunderkind

Mo, Feb 07, 2005 23:50
Antworten mit Zitat

Testen ist die einzige Möglichkeit. Es gibt (meines Wissen) schlicht keine einfache Funktion die z.B. alle Primzahlen zwischen x und y errechnet. Zum Testen aber, ob eine Zahl eine Primzahl ist oder nicht, gibt es mehrere Verfahren.

	darkshadow	Di, Feb 08, 2005 0:03 Antworten mit Zitat
>> S U C H E <<

darkshadow

Di, Feb 08, 2005 0:03
Antworten mit Zitat

>> S U C H E <<

	Rallimen Sieger des 30-EUR-Wettbewerbs	Di, Feb 08, 2005 0:27 Antworten mit Zitat
http://de.wikipedia.org/wiki/Primzahltest habe gerade gesehen das der Link schon versteckt bei Wunderkind steht! Mini Prg Zahlen bis 50 Code: [AUSKLAPPEN] [EINKLAPPEN] For i = 1 To 50 Step 2 teilbar = 0 For teiler = 2 To (i/2) If i Mod teiler = 0 Then teilbar = 1 : Exit Next If teilbar = 0 Then Print i Next WaitKey
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Di, Feb 08, 2005 0:27
Antworten mit Zitat

http://de.wikipedia.org/wiki/Primzahltest
habe gerade gesehen das der Link schon versteckt bei Wunderkind steht!
Mini Prg
Zahlen bis 50
Code: [AUSKLAPPEN]

For i = 1 To 50 Step 2
teilbar = 0
For teiler = 2 To (i/2)
If i Mod teiler = 0 Then teilbar = 1 : Exit
Next
If teilbar = 0 Then Print i
Next

WaitKey

[BB2D | BB3D | BB+]

	Mastakiller	Di, Feb 08, 2005 14:15 Antworten mit Zitat
oh vielen dank für das prog

Mastakiller

Di, Feb 08, 2005 14:15
Antworten mit Zitat

oh vielen dank für das prog Very Happy

	wunderkind	Di, Feb 08, 2005 18:08 Antworten mit Zitat
Primzahlen sind faszinierend. Ich habe mir heute unterwegs noch Gedanken zum Thema gemacht. Spielereien im Kopf . Mir ist es nicht gelungen, zuverlässig Primzahlen zu bilden. Zum Beispiel beim Produkt zweier Primzahlen + 1 oder +2. Das funktioniert nicht immer. Ich dachte eine Behauptung zu kennen, nach der etwas ähnliches gilt. Ich konnte aber auch jetzt nichts dazu finden. Interessant ist, dass der Quotient einer Primzahl und ihrer vorangegangenen Primzahl irgendwie zwischen 3 und 2 bewegt.

wunderkind

Di, Feb 08, 2005 18:08
Antworten mit Zitat

Primzahlen sind faszinierend. Ich habe mir heute unterwegs noch Gedanken zum Thema gemacht. Spielereien im Kopf Wink

. Mir ist es nicht gelungen, zuverlässig Primzahlen zu bilden. Zum Beispiel beim Produkt zweier Primzahlen + 1 oder +2. Das funktioniert nicht immer. Ich dachte eine Behauptung zu kennen, nach der etwas ähnliches gilt. Ich konnte aber auch jetzt nichts dazu finden. Interessant ist, dass der Quotient einer Primzahl und ihrer vorangegangenen Primzahl irgendwie zwischen 3 und 2 bewegt.

	Dreamora	Di, Feb 08, 2005 18:13 Antworten mit Zitat
Eine relativ gute Methode um Primzahlen zu finden ist 2^n +- 1, wenn man grad ma auf die schnelle Mal etwas braucht zb für Hashing oder Verschlüsselung.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Di, Feb 08, 2005 18:13
Antworten mit Zitat

Eine relativ gute Methode um Primzahlen zu finden ist 2^n +- 1, wenn man grad ma auf die schnelle Mal etwas braucht zb für Hashing oder Verschlüsselung.

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	wunderkind	Di, Feb 08, 2005 18:32 Antworten mit Zitat
@Dreamora Wenn ich alle haben möchte, dann fehlen mir bei deiner Methode ja unter 20 schon 2 Primzahlen: Code: [AUSKLAPPEN] [EINKLAPPEN] 2^1 = 2 (+/- 0) = 2 2^2 = 4 (+/- 1) = 3 & 5 2^3 = 8 (+/- 1) = 7 2^4 = 16 (+/- 1) = 17 Vielleicht kommt über den Ast heran, dass sich jeder Primzahl aus Faktoren von Primzahlen plus 1 darstellen lassen (von der 2 einmal abgesehen)?! Z.B.: Code: [AUSKLAPPEN] [EINKLAPPEN] 5 = 2 * 2 + 1 7 = 2 * 3 + 1 11 = 2 * 5 + 1 13 = 2 * 2 * 3 + 1 17 = 2 * 2 * 2 * 2 + 1 19 = 2 * 3 * 3 + 1

wunderkind

Di, Feb 08, 2005 18:32
Antworten mit Zitat

@Dreamora

Wenn ich alle haben möchte, dann fehlen mir bei deiner Methode ja unter 20 schon 2 Primzahlen:

Code: [AUSKLAPPEN]

2^1 = 2 (+/- 0) = 2
2^2 = 4 (+/- 1) = 3 & 5
2^3 = 8 (+/- 1) = 7
2^4 = 16 (+/- 1) = 17

Vielleicht kommt über den Ast heran, dass sich jeder Primzahl aus Faktoren von Primzahlen plus 1 darstellen lassen (von der 2 einmal abgesehen)?! Z.B.:

Code: [AUSKLAPPEN]

5 = 2 * 2 + 1
7 = 2 * 3 + 1
11 = 2 * 5 + 1
13 = 2 * 2 * 3 + 1
17 = 2 * 2 * 2 * 2 + 1
19 = 2 * 3 * 3 + 1

	Dreamora	Di, Feb 08, 2005 18:37 Antworten mit Zitat
Wenn du sie suchen willst, so wurde oben ja bereits die Wiki angegeben wo mit dem Sieb ein relativ effizienter Algorithmus angegeben wird. Dachte hier eher an die Erzeugung einer Primzahl ohne erst 1000 Zahlen durchzuprobieren ... Und das mit dem Ast ist ziemlich klar, da man so in der "naivsten" Variante eine Primzahl testet ( Primfaktorzerlegung ).
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Di, Feb 08, 2005 18:37
Antworten mit Zitat

Wenn du sie suchen willst, so wurde oben ja bereits die Wiki angegeben wo mit dem Sieb ein relativ effizienter Algorithmus angegeben wird.
Dachte hier eher an die Erzeugung einer Primzahl ohne erst 1000 Zahlen durchzuprobieren ...

Und das mit dem Ast ist ziemlich klar, da man so in der "naivsten" Variante eine Primzahl testet ( Primfaktorzerlegung ).

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	wunderkind	Di, Feb 08, 2005 18:41 Antworten mit Zitat
Ich habe selbst habe den Link oben auch geposted . Ich hatte mir nur Gedanken darüber gemacht, ob es einen Algorithmus gibt, der alle Primzahlen zwischen m und n erzeugt. Bisher gingen wir immer davon aus, dass wir eine Zahlen haben und prüfen, ob sie Primzahlen sind oder nicht. Nichts anderes macht auch das Sieb von Eratosthenes: Auf diese Weise werden Zahlen eleminiert und Primzahlen bleiben über.

wunderkind

Di, Feb 08, 2005 18:41
Antworten mit Zitat

Ich habe selbst habe den Link oben auch geposted Wink

. Ich hatte mir nur Gedanken darüber gemacht, ob es einen Algorithmus gibt, der alle Primzahlen zwischen m und n erzeugt. Bisher gingen wir immer davon aus, dass wir eine Zahlen haben und prüfen, ob sie Primzahlen sind oder nicht. Nichts anderes macht auch das Sieb von Eratosthenes: Auf diese Weise werden Zahlen eleminiert und Primzahlen bleiben über.

	Randall Flagg	Di, Feb 08, 2005 18:46 Antworten mit Zitat
ihr macht Blitzbasic in der Schule??? Ihr glücklichen!! Wir machen nur COMAL. blitzbasic ist unserem Lehrer zu einfach

Randall Flagg

Di, Feb 08, 2005 18:46
Antworten mit Zitat

ihr macht Blitzbasic in der Schule???

Ihr glücklichen!!
Wir machen nur COMAL.

blitzbasic ist unserem Lehrer zu einfach

	Mogon	Mi, Feb 09, 2005 12:15 Antworten mit Zitat
Servus! Hab mal was kleines gemacht. Kann die Primzahlen in einem beliebigen Bereich rausfinden und in eine Datei schreiben, wenn gewünscht, auch wenn die Speicher-Routine aus mir unerfindlichen Gründen streikt Es braucht für die Primzahlen zwischen 1 und 50000 ungefähr 36 Sekunden auf nem 3000+er. Ist allerdings noch nicht so ganz ausgereift mit dem Goto und so... Code: [AUSKLAPPEN] [EINKLAPPEN] Print "Eine Primzahl ist eine Zahl, die nur durch 1 und sich selbst teilbar ist." Print "" zahlenraum = Input("Bitte geben Sie die Zahl ein, bis zu der die Primzahlen errechnet werden sollen: ") Print "" .abspeichern Print "Moechten Sie die errechneten Primzahlen in einer Datei abspeichern?" speichern = Input("1:Ja 0:Nein Antwort: ") If speichern < 0 And speichern > 1 Then Print "" Print "Bitte geben Sie eine gültige Antwort ein!" Print "" Goto abspeichern EndIf Dim zahl(zahlenraum) For H = 1 To zahlenraum zahl(H) = 1 Next Print "Primzahlen:" For I = 1 To zahlenraum For J = 2 To I - 1 If I Mod J = 0 Then zahl(I) = 0 Next If zahl(I) = 1 Then Print I If zahl(I) = 1 Then gefunden = gefunden + 1 Next If speichern = 1 Then DeleteFile "primzahlen.txt" datei = WriteFile("primzahlen.txt") For K = 1 To zahlenraum If zahl(K) = 1 Then WriteLine datei, K geschrieben = geschrieben + 1 EndIf Next EndIf Repeat Until geschrieben = gefunden Print "" If speichern = 1 Then Print "Zahlen gespeichert als primzahlen.txt" Print "" Print "Primzahlen gefunden: " + gefunden Print "Primzahlen geschrieben: " + geschrieben WaitKey()

Mogon

Mi, Feb 09, 2005 12:15
Antworten mit Zitat

Servus!

Hab mal was kleines gemacht. Kann die Primzahlen in einem beliebigen Bereich rausfinden und in eine Datei schreiben, wenn gewünscht, auch wenn die Speicher-Routine aus mir unerfindlichen Gründen streikt Laughing

Es braucht für die Primzahlen zwischen 1 und 50000 ungefähr 36 Sekunden auf nem 3000+er.

Ist allerdings noch nicht so ganz ausgereift mit dem Goto und so... Embarassed

Code: [AUSKLAPPEN]

Print "Eine Primzahl ist eine Zahl, die nur durch 1 und sich selbst teilbar ist."
Print ""
zahlenraum = Input("Bitte geben Sie die Zahl ein, bis zu der die Primzahlen errechnet werden sollen: ")
Print ""
.abspeichern
Print "Moechten Sie die errechneten Primzahlen in einer Datei abspeichern?"
speichern = Input("1:Ja 0:Nein Antwort: ")
If speichern < 0 And speichern > 1 Then
Print ""
Print "Bitte geben Sie eine gültige Antwort ein!"
Print ""
Goto abspeichern
EndIf

Dim zahl(zahlenraum)

For H = 1 To zahlenraum
zahl(H) = 1
Next

Print "Primzahlen:"

For I = 1 To zahlenraum
For J = 2 To I - 1
   If I Mod J = 0 Then zahl(I) = 0
Next
If zahl(I) = 1 Then Print I
If zahl(I) = 1 Then gefunden = gefunden + 1
Next

If speichern = 1 Then
DeleteFile "primzahlen.txt"
datei = WriteFile("primzahlen.txt")
For K = 1 To zahlenraum
   If zahl(K) = 1 Then
      WriteLine datei, K
      geschrieben = geschrieben + 1
   EndIf
Next
EndIf

Repeat
Until geschrieben = gefunden
Print ""
If speichern = 1 Then Print "Zahlen gespeichert als primzahlen.txt"
Print ""
Print "Primzahlen gefunden: " + gefunden
Print "Primzahlen geschrieben: " + geschrieben

WaitKey()

	skey-z	Mi, Feb 09, 2005 14:45 Antworten mit Zitat
ich habs mal durchlaufen lassen, bis 50000, bei mir auf nem 2200+ braucht der locker 2min. aber ist ein nettes kleines programm^^

skey-z

Mi, Feb 09, 2005 14:45
Antworten mit Zitat

ich habs mal durchlaufen lassen, bis 50000, bei mir auf nem 2200+ braucht der locker 2min.

aber ist ein nettes kleines programm^^

	BladeRunner Moderator	Mi, Feb 09, 2005 14:59 Antworten mit Zitat
Code: [AUSKLAPPEN] [EINKLAPPEN] For J = 2 To I - 1 ist unnötig, es reicht : Code: [AUSKLAPPEN] [EINKLAPPEN] for J = 2 to I.5 (der größte Teiler würde die Zahl ja halbieren) Ausserdem würde ich : Code:* [AUSKLAPPEN] [EINKLAPPEN] for i= 1 to Zahlenraum step 2 nehmen- auf gerade Zahlen testen ist ja unsinnig.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Mi, Feb 09, 2005 14:59
Antworten mit Zitat

Code: [AUSKLAPPEN]

For J = 2 To I - 1

ist unnötig, es reicht :
Code: [AUSKLAPPEN]

for J = 2 to I*.5

(der größte Teiler würde die Zahl ja halbieren)

Ausserdem würde ich :
Code: [AUSKLAPPEN]

for i= 1 to Zahlenraum step 2

nehmen- auf gerade Zahlen testen ist ja unsinnig.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	Mogon	Mi, Feb 09, 2005 16:08 Antworten mit Zitat
Danke ! Werds sofort optimieren und dann mal Speed-Tests machen...

Mogon

Mi, Feb 09, 2005 16:08
Antworten mit Zitat

Danke ! Werds sofort optimieren und dann mal Speed-Tests machen... Very Happy

	Triton	Mi, Feb 09, 2005 17:36 Antworten mit Zitat
wunderkind hat Folgendes geschrieben: Vielleicht kommt über den Ast heran, dass sich jeder Primzahl aus Faktoren von Primzahlen plus 1 darstellen lassen Naja, JEDE Zahl lässt sich als Produkt aus Primzahlen darstellen, soweit ich weiß. BladeRunner hat Folgendes geschrieben: Code: [AUSKLAPPEN] [EINKLAPPEN] For J = 2 To I - 1 ist unnötig, es reicht : Code: [AUSKLAPPEN] [EINKLAPPEN] for J = 2 to I*.5 (der größte Teiler würde die Zahl ja halbieren) Bis zur Wurzel der Zahl testen reicht auch. Desweiteren gibts noch ne menge weiterer Vereinfachungen, die aus Zahlentheoretischen Überlgungen hervorgehen, z.B kann man durch Ausschließen von folgenden Zahlen einen großteil der Zahlen rausfiltern und somit das verfahren verschnellern: - 0,2,4,5,6,8 hinten - deren quersumme durch 3 teilbar ist - deren quersumme der letzten beiden ziffern durch 8 teilbar ist - ...
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Mi, Feb 09, 2005 17:36
Antworten mit Zitat

wunderkind hat Folgendes geschrieben:

Vielleicht kommt über den Ast heran, dass sich jeder Primzahl aus Faktoren von Primzahlen plus 1 darstellen lassen

Naja, JEDE Zahl lässt sich als Produkt aus Primzahlen darstellen, soweit ich weiß.

BladeRunner hat Folgendes geschrieben:

Code: [AUSKLAPPEN]

For J = 2 To I - 1

ist unnötig, es reicht :
Code: [AUSKLAPPEN]

for J = 2 to I*.5

(der größte Teiler würde die Zahl ja halbieren)

Bis zur Wurzel der Zahl testen reicht auch.
Desweiteren gibts noch ne menge weiterer Vereinfachungen, die aus Zahlentheoretischen Überlgungen hervorgehen, z.B kann man durch Ausschließen von folgenden Zahlen einen großteil der Zahlen rausfiltern und somit das verfahren verschnellern:

- 0,2,4,5,6,8 hinten
- deren quersumme durch 3 teilbar ist
- deren quersumme der letzten beiden ziffern durch 8 teilbar ist
- ...

Coding: silizium-net.de | Portfolio: Triton.ch.vu

Übersicht

BlitzBasic

Beginners-Corner

Nach Oben

BlitzBasic Portal

Programm um Primzahlen herauszufinden

Betreff: Programm um Primzahlen herauszufinden