| Autor |
Beitrag |
    
Fionn (fionn)
Mitglied
Benutzername: fionn
Nummer des Beitrags: 21
Registriert: 02-2002
| | Veröffentlicht am Mittwoch, den 29. Mai, 2002 - 19:07: | 
|
hallo, vielleicht gehoert das nicht in das forum, doch es interessiert mich einfach.
Ich habe eine Ganzzahlige Zahl, möchte nun wissen ob dies eine primzahl ist. Wie kann ich das nachprüfen ? . "Fermats kleiner Satz", vielleicht kann mir das jemand kurz erklären, wäre echt nett, gruss fionn |
Gast2
Unregistrierter Gast
| | Veröffentlicht am Mittwoch, den 29. Mai, 2002 - 19:52: |
|
Primzahl => Mathe => klar gehört das hier hin!
;-)
Primzahltest (kenn ich bisher nur von der Schule):
Du nimmst die Wurzel deiner Zahl. Dann schaust du, welche nächst kleinste Zahl wieder Primzahl (pk gennant) ist. Nun mußt du zum Test nach und nach deine Zahl durch alle Primzahlen bis pk teilen. Geht die Teilung für alle Primzahlen nicht auf, so hast du eine Primzahl.
Beispiel:
Ist 221 Primzahl?
W(221)=14,8... => ~14
Wir brauchen also die Primzahlen bis 14:
{2,3,5,7,11,13}
Test:
221/2 ->klappt nicht
221/3 ->klappt nicht
221/5 ->klappt nicht
221/7 ->klappt nicht
221/11 -> klappt nicht
221/13=17 => Keine Primzahl!
Nun weiteres Beispiel:
83 Primzahl?
W(83)=9,1...
Primzahlen bis 9:
{2,3,5,7}
83/2 -> klappt nicht
83/3 -> klappt nicht
83/5 -> klappt nicht
83/7 -> klappt nicht
=> 83 ist Primzahl!
Vielleicht gibt es elegantere Wege, mal abwarten, ob ein(e) andere(r) schlauer/schlaue Student(in) etwas weiter ist wie wir (hatten noch keine Zahlentheorie)!
Tschau
Gast2 |
Fionn (fionn)
Mitglied
Benutzername: fionn
Nummer des Beitrags: 22
Registriert: 02-2002
| | Veröffentlicht am Donnerstag, den 30. Mai, 2002 - 10:50: |
|
prima, ist ja gar nicht so schweer. Danke für deine Hilfe. Wie ist das denn, wenn man eine Primzahl einer 7 oder 10 stelligen Zahl überprüfen will ? die Wurzel aus einer Mio.= 1000, jetzt muss ich von 1 - 1000 alle Primzahlen durchtesten , gibt es da nicht einen eleganteren weg ?
gruss fionn |
Gast2
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 30. Mai, 2002 - 13:52: |
|
Hi, würd dir ja gern eine elegantere Methode anbieten, nur kenn ich bis dato leider keine!
Einfach mal abwarten!
Tschau
Gast2 |
Fionn (fionn)
Mitglied
Benutzername: fionn
Nummer des Beitrags: 23
Registriert: 02-2002
| | Veröffentlicht am Donnerstag, den 30. Mai, 2002 - 15:11: |
|
klar, kein problem. Mir ist aufgefallen, das ALLE Primzahlen immer mit der Zahlen 9,7,3,1 aufhören, bis jetzt habe ich noch keine Primzahl gefunden, die nicht mit diesen Zahlen aufhört.gruss fionn |
Robert (emperor2002)
Mitglied
Benutzername: emperor2002
Nummer des Beitrags: 34
Registriert: 04-2002
| | Veröffentlicht am Donnerstag, den 30. Mai, 2002 - 15:19: |
|
Das mit den Endziffern is klar:
2,4,6,8 sind durch 2 teilbar und eine Zahl mit Endziffer 5 ist ja immer durch 5 teilbar =)
Daher bleiben nur noch die anderen Endziffern als Kandidaten für Primzahlen übrig!
MFG
Robert
Robert Klinzmann
Schüler des EHGs
mailto: Emperor2002@Web.de
|
Niels (niels2)
Mitglied
Benutzername: niels2
Nummer des Beitrags: 31
Registriert: 06-2001
| | Veröffentlicht am Donnerstag, den 30. Mai, 2002 - 15:39: |
|
Hi Fion,
deine Regel mit den Endziffern ist korrekt.
Aus der Tatsache das angeblich alle Primzahlen mit
9,7,3,1 aufhören darf man nicht schließen, dass alle Zahlen mit diesen Endziffern Primzahlen wären.
Beispiele:
99 endet mit 9 ist aber keine Primzahl
27 endet mit 7 ist aber keine Primzahl
33 endet mit 3 ist aber keine Primzahl
81 endet mit 1 ist aber keine Primzahl
Das übliche Verfahren um Primzahlen zu bestimmen nent man "Das Sieb des Erathostenes"
Gruß N.
|
Carmichael (carmichael)
Erfahrenes Mitglied
Benutzername: carmichael
Nummer des Beitrags: 142
Registriert: 02-2001
| | Veröffentlicht am Donnerstag, den 30. Mai, 2002 - 18:10: |
|
Hi,
hier zwei Primzahlentest im Zusammenhang mit kleinem Fermat (nur Angabe):
1) Findet man ein b (b positiv und kleiner n) mit b^(n-1) - 1 nicht durch n teilbar, dann ist n keine Primzahl.
2) Findet man ein b (b positiv und kleiner n), sodass b^(n-1) - 1 durch n teilbar und b^([n-1)/d] - 1 für keinen Primteiler d von n-1 durch n teilbar ist, so ist n Primzahl.
Gruß Carmichael
|
Gast2
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 30. Mai, 2002 - 20:08: |
|
@fionn:
Da du bei Primzahlentest ja auch teilen mußt, gibt es gewisse Rechenregeln, mit denen du bei folgenden Zahlen die Teilbarkeit durch diese "durch schnelles Hingucken" auch "sehen" kannst:
Eine Zahl ist teilbar durch
2, wenn die letzte Ziffer eine gerade Zahl ist;
4, wenn die letzten beiden Ziffern eine durch 4 teilbare Zahl darstellen;
8, wenn die letzten 3 Ziffern eine durch 8 teilbare Zahl darstellen;
5, wenn die letzte Ziffer entweder 0 oder 5 ist
25, wenn die letzten 2 Ziffern eine durch 25 teilbare Zahl darstellen;
3, wenn ihre Quersumme durch 3 teilbar ist [Quersumme ist die Summe der Ziffern, also z.B. bei 27 ist Quersumme 2+7=9 und 9 ist durch 3 teilbar, also ist 27 durch 3 teilbar];
9, wenn ihre Quersumme durch 9 teilbar ist
11, wenn ihre alternierende Quersumme durch 11 teilbar ist
Alternierende Quersumme ist die (Summe der Ziffern an ungeradzahligen Stellen) - (die Summe der Ziffern an geradzahligen Stellen):
Beispiel:
85976
Summe der Ziffern an ungeradzahligen Stellen:
8+9+6=23
Summe der Ziffern an geradzahligen Stellen:
5+7=12
Summe der Ziffern an ungeradzahligen Stellen) - (die Summe der Ziffern an geradzahligen Stellen)=alternierende Quersumme
=23-12=11 und 11 ist bekanntlich durch 11 teilbar!
Also ist 85976 durch 11 teilbar (und somit keine Primzahl, was man hier auch an der letzten 6 gesehen hätte, da 6 gerade ist!)!
Tschau
Gast2 |
Fionn (fionn)
Mitglied
Benutzername: fionn
Nummer des Beitrags: 24
Registriert: 02-2002
| | Veröffentlicht am Donnerstag, den 30. Mai, 2002 - 20:16: |
|
ok, das ist verständlich. @carmichael Vielleicht koenntest du mir die Erste Rechnung an einem Beispiel vorrechnen.
1) Findet man ein b (b positiv und kleiner n) mit
b^(n-1) - 1 nicht durch n teilbar, dann ist n keine Primzahl.
Vielen Dank für die Hilfe,
gruss fionn |
Gast2
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 30. Mai, 2002 - 20:26: |
|
Hab gerade deine Antwort/Frage gesehen, also z.B.
n=25
nimm b=2<25
(2^24)-1=16777216-1=16777215 und ist damit nicht durch 25 teilbar!
Also ist 25 keine Primzahl!
Tschau
Gast2 |
Fionn (fionn)
Mitglied
Benutzername: fionn
Nummer des Beitrags: 25
Registriert: 02-2002
| | Veröffentlicht am Montag, den 03. Juni, 2002 - 16:27: |
|
Prima, das mit der rechnung funktioniert wunderbar.Für b=2 funktioniert auch immer, ich versthe nur nicht wieso ? Ich versuche ein Programm in delphi zu schreiben, was mir alle Primzahlen berechnen soll.Leider ist das nicht so einfach wie es scheint.Vielleicht kann mir jemand einen Tipp geben, wie ich von der Beweisführung zu einer konkreten ermittlung gelange.Geht das überhaubt?Sonst müssen halt alle Zahlen, die mit 9,7,3,1 enden abgearbeitet werden.Nach dem verfahren wie es "Carmichael" und "gast2" beschrieben haben, freue mich über Ideen und Tipps, Gruss Fionn
|
Gast2
Unregistrierter Gast
| | Veröffentlicht am Montag, den 03. Juni, 2002 - 19:36: |
|
Hallo Fionn,
hoffe, du kennst die Programmiersprache Java:
http://www.cs.uni-magdeburg.de/~fbeyer/Mathe-Programme/SiebDesEratosthenes.java
Tschau
Gast2 |
Niels (niels2)
Mitglied
Benutzername: niels2
Nummer des Beitrags: 36
Registriert: 06-2001
| | Veröffentlicht am Dienstag, den 04. Juni, 2002 - 08:01: |
|
Hi Fion,
schau mal hier vorbei:
http://www.uni-karlsruhe.de/~uv6v/primzahlen/primzahlen.html
Gruß N. |
Fionn (fionn)
Mitglied
Benutzername: fionn
Nummer des Beitrags: 26
Registriert: 02-2002
| | Veröffentlicht am Dienstag, den 04. Juni, 2002 - 14:15: |
|
@Niels, das ist genau was ich gesucht habe, ausgezeichnet. Ich habe einen Primzahlentest im Zusammenhang mit dem kleinem Satz von Fermat, programmiert.Leider ist der Computer anhand eines BufferOverfloas abgestürtzt. Es geht leider nur bis zur 10-tausender Marke, in der Rechnung, kommt somit ein zwischenergebniss von p hoch 10-tausend zustande.Danke für die Links, hilft mir enorm weiter, Gruss Fionn |
|
