| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
hello
Anmeldungsdatum: 15.04.2010
Beiträge: 34
|
 Verfasst am: 10.06.2010, 12:44 Titel: FreeBASIC - Primzahl erkennen - wie ? |
 |
|
Ist wichtig, danke für alle Antworten 
_________________
Regards |
|
| Nach oben |
|
 |
HorstD
Anmeldungsdatum: 01.11.2007
Beiträge: 110
|
| Verfasst am: 10.06.2010, 13:34 Titel: |
|
|
| Zitat: | | Primzahl erkennen - wie ? |
Eine Primzahl erkennst du daran, dass sie sich nur durch 1 oder sich selbst teilen lässt. |
|
| Nach oben |
|
|
Sebastian
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 5969
Wohnort: Deutschland
|
|
| Nach oben |
|
|
hello
Anmeldungsdatum: 15.04.2010
Beiträge: 34
|
| Verfasst am: 10.06.2010, 15:13 Titel: |
|
|
Oder mit MOD
| Code: | IF (a MOD b <> 0) THEN
[...]
END IF |
Oder ??
_________________
Regards |
|
| Nach oben |
|
|
Sebastian
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 5969
Wohnort: Deutschland
|
| Verfasst am: 10.06.2010, 15:49 Titel: |
|
|
Mit MOD kannst du den Rest einer Division ermitteln.
Beispiel:
| Code: | PRINT "19 geteilt durch 8 ist " & (19\8) & " Rest " & (19 MOD 8)
SLEEP |
MOD spielt für einen Primzahltest natürlich eine Rolle, aber allein damit kann man noch nicht herausfinden, ob eine Zahl prim ist oder nicht. Du kannst schließlich nur einen Divisor auf einmal angeben.
In dem von mir verlinkten Code aus der QBasic-Monster-FAQ wird auch MOD verwendet, um zu prüfen, ob eine Division restbehaftet war.
Wenn
dann ist Y ein ganzzahliger Teiler von X.
_________________
Die gefährlichsten Familienclans | Opas Leistung muss sich wieder lohnen - für 6 bis 10 Generationen! |
|
| Nach oben |
|
|
MOD
Fleißiger Referenzredakteur
Anmeldungsdatum: 10.09.2007
Beiträge: 1003
|
| Verfasst am: 10.06.2010, 17:41 Titel: |
|
|
Was ist mit mir?  |
|
| Nach oben |
|
|
darkinsanity
aka sts
Anmeldungsdatum: 01.11.2006
Beiträge: 456
|
| Verfasst am: 10.06.2010, 18:20 Titel: |
|
|
Wie schon gesagt ist eine Primzahl eine Zahl, die nur durch 1 und sich selbst teilbar ist. Im Umkehrschluss heist das, dass eine Primzahl nicht durch andere Zahlen außer 1 und sich selbst teilbar ist. Und genauso findest du heraus, ob eine Zahl eine Primzahl ist: Du überprüftst, ob eine Zahl von 2 bis zur möglichen Primzahl existiert, die deine Zahl ohne Rest teilt. Gibt es eine solche Zahl, ist deine Zahl keine Primzahl.
Genau genommen musst du nur 2 und die ungeraden Zahlen bis zur Quadratwurzel der Zahl überprüfen. Folgender Code tut genau das:
| Code: | sub IsPrim (ByVal zahl as UINTEGER)
dim prim as BYTE = 1
if (zahl mod 2) = 0 then
prim = 0
else
for counter as UINTEGER = 3 to int(sqr(zahl))+1 step 2
if (zahl mod counter) = 0 then
prim = 0
exit for
end if
next
end if
if prim = 1 then
print zahl & " ist eine Primzahl."
else
print zahl & " ist keine Primzahl."
end if
end sub |
Gar nicht so schwer 
Und gerade bei großen Zahlen hilft es sehr, dass nur jede zweite Zahl bis zur Quadratwurzel überprüft wird.
_________________
Traue keinem Computer, den du nicht aus dem Fenster werfen kannst -- Steve Wozniak |
|
| Nach oben |
|
|
Stueber
Anmeldungsdatum: 07.07.2008
Beiträge: 202
|
| Verfasst am: 11.06.2010, 14:07 Titel: |
|
|
| Sieb des Eratosthenes, ist zwar ineffizient aber funktioniert problemlos mit jeder Zahl. |
|
| Nach oben |
|
|
MisterD
Anmeldungsdatum: 10.09.2004
Beiträge: 3071
Wohnort: bei Darmstadt
|
| Verfasst am: 11.06.2010, 14:44 Titel: |
|
|
das ist nur ineffizient solang man nur eine einzige zahl prüfen will
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra |
|
| Nach oben |
|
|
hello
Anmeldungsdatum: 15.04.2010
Beiträge: 34
|
| Verfasst am: 11.06.2010, 14:49 Titel: |
|
|
| MisterD hat Folgendes geschrieben: | | das ist nur ineffizient solang man nur eine einzige zahl prüfen will |
Wieso nur eine? Klappt problemlos mit mehreren (While-Schleife).
__________________
Danke
_________________
Regards |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4704
Wohnort: ~/
|
| Verfasst am: 11.06.2010, 15:02 Titel: |
|
|
Wenn du eine Liste aller Primzahlen von 2 bis ?? speichern willst, empfiehlt sich der Sieb des Eratosthenes; wenn du nur eine prüfen willst, ist der Sieb ineffizient. Dass du so oder so auch mehrere Primzahlen prüfen kannst, steht außer Frage.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
The_Muh
aka Mark Aroni
Anmeldungsdatum: 11.09.2006
Beiträge: 718
|
| Verfasst am: 11.06.2010, 15:12 Titel: |
|
|
| Code: | dim as integer a = 2, n
for i as integer = 2 to 30
n = i
if (a^(n-1) mod n = 1 ) then ? n &" primzahl"
next |
Soweit ich das sehe funktioniert der test.
Erklärung: n ist die zu testende Zahl. Den code hab ich hiervon abgeleitet: Lucas-Test
_________________
// nicht mehr aktiv // |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4704
Wohnort: ~/
|
| Verfasst am: 11.06.2010, 15:36 Titel: |
|
|
Wenn du natürlich nur bis 30 testest, dann funktioniert der Test sehr gut.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
hello
Anmeldungsdatum: 15.04.2010
Beiträge: 34
|
| Verfasst am: 11.06.2010, 18:36 Titel: |
|
|
| The_Muh hat Folgendes geschrieben: | | Code: | dim as integer a = 2, n
for i as integer = 2 to 30
n = i
if (a^(n-1) mod n = 1 ) then ? n &" primzahl"
next |
Soweit ich das sehe funktioniert der test.
Erklärung: n ist die zu testende Zahl. Den code hab ich hiervon abgeleitet: Lucas-Test |
Ja, sollte, danke
_________________
Regards |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4704
Wohnort: ~/
|
| Verfasst am: 11.06.2010, 18:55 Titel: |
|
|
Der Code scheitert aus drei Gründen. Erstens ist in FreeBASIC ein Integer auf 32 Bit beschränkt; was das für die zu untersuchenden Primzahlen bedeutet, kannst du selbst überlegen. Zweitens testet es nur a=2, damit kann es sein, dass irgendwann eine Primzahl auftaucht, die nicht gefunden wird (weil für sie ein anderes a benötigt wird - ist dir aufgefallen, dass 2 nicht als Primzahl erkannt wird?). Drittens testet der Code nur eine von zwei Bedingungen, also kann es sein, dass eine Zahl gefunden wird, die gar keine Primzahl ist. Um Punkt 2 und 3 musst du dir aber wegen Punkt 1 keine Gedanken machen.
Ich weiß übrigens nicht, ob es sich bei dem Satz um eine "genau dann wenn"-Aussage handelt, ich bezweifle es eher.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
The_Muh
aka Mark Aroni
Anmeldungsdatum: 11.09.2006
Beiträge: 718
|
| Verfasst am: 11.06.2010, 19:54 Titel: |
|
|
Der Schnipsel ist das ergebnis von 5 minuten arbeit (wikipedia-recherche mit einbezogen). Ich bin kein mathematiker, deswegen hab ich keine ahnung ob das ding nun richtig funktioniert oder nicht. War halt nur ein vorschlag.
_________________
// nicht mehr aktiv // |
|
| Nach oben |
|
|
bubu
Anmeldungsdatum: 21.02.2010
Beiträge: 13
|
| Verfasst am: 12.06.2010, 13:02 Titel: |
|
|
Ich hab da sonst noch ein ganz gutes Programm:
| Code: |
dim as integer WinBreite,WinHoehe
screeninfo WinBreite,WinHoehe
screenres WinBreite,WinHoehe,8,,0
dim AS UINTEGER feld=1000000000,z
locate 10,20:input "Maximum:",z
if z<10000 then z=10000
cls
DIM AS SINGLE s=TIMER
REDIM as ubyte atrib(feld)
DIM AS UINTEGER i,n,x=11,y=3,zahl=4
print "2 3 5 7 ";
for i=11 to z step 2
DO
IF x*y>z THEN x=3:y=y+2 ELSE x=x+2
IF y^2>z THEN EXIT DO
atrib(x*y)=1
loop
next i
FOR i=11 TO z STEP 2
IF atrib(i)=0 and i>9 THEN zahl=zahl+1:PRINT i;" ";
NEXT i
s=TIMER-s
print
print
print "Anzahl Prim: ";zahl,LEFT(STR(s),5);" Sek."
SLEEP
END
|
|
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4704
Wohnort: ~/
|
| Verfasst am: 12.06.2010, 14:19 Titel: |
|
|
Das Programm hat ein paar handwerkliche Mängel, wie die überflüssige FOR-Schleife um die DO-Schleife herum (die DO-Schleife verrichtet bereits die gesamte Arbeit!) und eine Abfrage i>9, wenn i doch bei 11 beginnt ... aber die dahinter stehende Idee ist spitze.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
bubu
Anmeldungsdatum: 21.02.2010
Beiträge: 13
|
| Verfasst am: 12.06.2010, 15:03 Titel: |
|
|
Ja, danke.
So ist es wohl etwas besser:
| Code: |
dim as integer WinBreite,WinHoehe
screeninfo WinBreite,WinHoehe
screenres WinBreite,WinHoehe,8,,0
dim AS UINTEGER feld=1000000000,z
locate 10,20:input "Maximum:",z
if z<10000 then z=10000
cls
DIM AS SINGLE s=TIMER
REDIM as ubyte atrib(feld)
DIM AS UINTEGER i,n,x=11,y=3,zahl=4
print "2 3 5 7 ";
DO
IF x*y>z THEN x=3:y=y+2 ELSE x=x+2
IF y^2>z THEN EXIT DO
atrib(x*y)=1
loop
FOR i=11 TO z STEP 2
IF atrib(i)=0 THEN zahl=zahl+1:PRINT i;" ";
NEXT i
s=TIMER-s
print
print
print "Anzahl Prim: ";zahl,LEFT(STR(s),5);" Sek."
SLEEP
END
|
|
|
| Nach oben |
|
|
vspickelen
Anmeldungsdatum: 12.06.2005
Beiträge: 13
Wohnort: Holland
|
| Verfasst am: 21.06.2010, 18:56 Titel: |
|
|
Praktisch, schnell und einfach:
| Code: | 'Der Miller-Rabin probabilistischer Primzahltest (1976)
'N < 2^63 (bis 19-stellig Dezimal)
Sub Modmlt (ByRef a As Ulongint, b As Ulongint, N As Ulongint)
If N Shr 32 Then
'Bauernmultiplikation mit modularen Reduktion
Dim As Ulongint p = a, q = b
a = 0: If q > p Then Swap p, q
While q > 0 ' Addieren und Verdoppeln
If q And 1 Then
a = (a + p) Mod N
End If
p = (p Shl 1) Mod N
q Shr= 1
Wend
Else ' max. 32-Bit
a = a * b Mod N
End If
End Sub
Dim d As Longint, sw As Integer
Dim As Ulongint N,k,N2,a,p,e
Dim As Uinteger t,i,j
Const z = 5 ' Anzahl der Zeugen
Const f = 100 / (1 Shl z * 2) ' Fehlklassierung
Cls : Randomize Timer
begin:
Print
Do: Input " N? ", N
Loop While N Shr 63
If N < 3 Then End
Print "N = "; N
If (N And 1) = 0 Then
Print "N ist gerade"
Goto begin
End If
k = N - 1: t = 0
While (k And 1) = 0 ' N-1 = ungerade(k) * (2^t)
k Shr= 1: t += 1
Wend
Print "k = "; k; " t = "; t
N2 = N Shr 1
For i = 1 TO z ' Miller-Rabin Test:
Do
a = 2 + Int(Rnd * 1022) ' zufälliger Zeuge
Loop Until a Mod N
Print "Zeuge: "; a
p = 1: e = k
While e > 0 ' Multiplizieren und Quadrieren
If e And 1 Then
Modmlt p, a, N
End If
Modmlt a, a, N
e Shr= 1
Wend
sw = (p <> 1) ' Falls N prim: a^k mod N = 1
For j = 1 To t ' oder (a^k)^ 2^j mod N = -1
sw And= (p <> N - 1) ' für einem j in [0, t - 1]
'
d = p: If p > N2 Then d -= N
Print "(a^k)^ 2^";j-1;" = ";d;" mod N"
'
Modmlt p, p, N ' Potenz quadrieren
Next j
Print "a^(N-1) = ";p;" mod N"
If sw Then Exit For
Next i
If sw Then
Print "N ist zusammengesetzt"
Else
Print "N ist wahrscheinlich prim (irr < ";LEFT(STR(f),5);"%)"
End If
Goto begin
End |
Natürlich steckt dahinter eine schöne Theorie, kurz:
Falls N prim (und N teilt nicht a) ist a^(N-1) = 1 modulo N.
In so einem 'Restklassenring nach einer Primzahl N' sind 1 und -1 die einzigen Quadratwurzeln von 1.
Findet die Suchschleife diese nicht, ist N ganz sicher zusammengesetzt.
Sonst könnte N tatsächlich prim, selten auch eine 'strenge Pseudoprimzahl' sein.
Letzten werden mit bestimmten Gewissheit durch Wiederholung abgefangen.
_______________________________________________________________
Langzahl-Fassung: http://largeint.sourceforge.net/Langzahl.htm |
|
| Nach oben |
|
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
