1 = Primzahl ???
Neue Frage »

16.09.2003, 23:26 Steve_FL Auf diesen Beitrag antworten »
1 = Primzahl ???
Wir hatten es ja grade von Primzahlen im Rangtiteltreff Augenzwinkern
Nun mal ne Frage zu Primzahlen:
gehört 1 auch dazu? Ich sage nicht, ein Kumpel lässt sich nicht davon überzeugen, dass 1 keine sei Augenzwinkern
Gibts da einen Beweis?

mfg
16.09.2003, 23:40 jama Auf diesen Beitrag antworten »

soweit ich weiß ist eine primzahl folgendermaßen definiert:

Eine natürliche Zahl n>2 und n=2 nennt man eine Primzahl, wenn sie nur 1 und n als Teiler besitzt.

wenn du nur den letzten teil nimmst, hätte dein freund recht Augenzwinkern
16.09.2003, 23:41 Thomas Auf diesen Beitrag antworten »

Hm.

1 ist keine Primzahl, weil sie halt einfach nicht dazugehört.

hier mal ein zitat von einer seite:

Zitat:

Eine Primzahl ist eine natürliche Zahl welche genau zwei Teiler hat. Weder die 0 noch die 1 werden üblicherweise als Primzahl bezeichnet. Die 0 wohl schon deswegen nicht, weil sie nicht durch sich selbst teilbar ist. Die 1 wird hauptsaechlich deshalb nicht als Primzahlzerlegung bezeichnet, weil sonst die Primfaktorzerlegung nicht mehr eindeutig wäre. (18 = 3 * 3 * 2 * 1 * 1 * 1 * 1 * 1 * ...).


http://www.wikiservice.at/dse/wiki.cgi?PrimZahl
16.09.2003, 23:42 BlackJack Auf diesen Beitrag antworten »

def:
eine zahl, die nur sich selber und 1 als teiler hat, ist eine primzahl.

sich selber wäre ja schon 1, deswegen hat die 1 nur einen teiler=> keine primzahl.
16.09.2003, 23:43 jama Auf diesen Beitrag antworten »

haha, war erster Big Laugh
17.09.2003, 00:08 DeGT Auf diesen Beitrag antworten »

Nimmt die Häufigkeit von Primzahlen eigentlich stellenweie ab oder ist das relativ konstant?

gibt es dazu irgendwelche Graphen?
 Anzeige 
 
17.09.2003, 01:12 Mathefreak Auf diesen Beitrag antworten »

Auch ich möchte hierzu einige Dinge sagen.

Die Gründe die bisher angeführt wurden, sind alle samt logisch und nachvollziehbar, allerdings ist nirgens definiert, dass 1 keine Primzahl ist. Aus den bisher genannten Gründen, lässt man sie aber bei Seite. Definiert ist allgemein nichts, wie so oft in der Mathematik.

Auf das Problem der Häufigkeit von Primzahlen kann man sehr leicht argumentieren. Je größer die Zahlen werden, desto mehr Primfaktoren haben sie in iher PFZ. Damit nimmt allerdings auch die Häufigkeit der Primzahlen in großen Bereichen ab. Es gibt hierzu einen sehr netten Satz:

Satz Tschebyscheff (1821-1894)

lim(x->oo) pi(x)/(x/ln(x)) =1, falls der Grenzwert existiert (**). Umgeformt heißt das:

ln(x)/x = pi(x), für x -> oo (*)

pi(x) ist hierbei die Anzahl der Primzahlen zwischen 2 und x. Man erkennt hier sofort, dass die Häufigkeit deutlich abnimmt.

Ich glaube Gauß stellte (*) auf und Tschebyscheff konnte (**) herleiten!
29.04.2004, 23:27 gast Auf diesen Beitrag antworten »

*möp*
29.04.2004, 23:35 sommer87 Auf diesen Beitrag antworten »

@gast: :spam: bitte.

deine dummen komentare kannst du dir auch sparen!!!

meinst du wirklich, dass dir deine sinnlosen antworten was bringen? (is ne rhetorische frage, auf die ich keine antwort will!)

wenn du ein problem mit jemdandem hast kannst du dies sicher mit jedem im ICQ oder per mail ausdiskutieren!
29.04.2004, 23:35 Deakandy Auf diesen Beitrag antworten »

Okee das war ja wieder ein Eintrag ohne vorher nachgedacht zu haben... Was macht denn ein Student der Mathematik, sei es Diplom oder Lehramt?
Sollte er sich nicht mit Mathe beschäftigen??
Also beschäftige dich erst mal mit Gedankentheorien...
04.05.2004, 12:33 SirJective Auf diesen Beitrag antworten »

Die Zahl 1 ist weder Primzahl noch zusammengesetzte Zahl. Diese beiden Begriffe sind nur fuer natuerliche Zahlen groesser als 1 definiert. Sinnvoll ist es, die 1 nicht als Primzahl zu betrachten, denn mit einer Primzahl 1

* waere die Primfaktorzerlegung nicht eindeutig (man haette beliebig viele Faktoren 1 drin)

* muesste man bei vielen Saetzen, in denen Primzahlen auftreten, die 1 wieder ausschliessen, da sie fuer 1 nicht gelten.

Ausserdem gibt es eine Verallgemeinerung des Begriffs der Primzahl auf andere mathematische Strukturen (Integritaetsringe genannt). Dort heissen sie dann Primelement und irreduzible Elemente (das sind zwei verschieden Dinge!), und haben viele Eigenschaften, die Primzahlen auch haben. In diesen Ringen gibt es auch so genannte Einheiten (das sind Teiler der 1), und Einheiten werden bei der Diskussion von Primelementen gar nicht betrachtet, sind also weder prim noch nicht prim. (Fuer die rationale Zahl 2/3 ist auch nicht definiert, ob sie "gerade" oder "ungerade" ist.)

Gruss,
SirJective
27.05.2004, 14:12 Silver (Gast) Auf diesen Beitrag antworten »

Hallo ihr, ich hab ma eine Frage wollte aber kein neues Thema eröffnen und zwar muss ich wissen wie man überprüfen kann ob eine Zahl eine Primzahl ist. Gibt es da eine Formel? Mit dem durch sich selbst und durch eins teilbar weiss ich schon, aber ich komm einfach nicht auf eine logische Formel, brauche diese Formel dringend für ein Programm, welches überprüft ob die eingebende Zahl auch eine Primzahl ist!

gruß

Silver
27.05.2004, 14:20 SirJective Auf diesen Beitrag antworten »

Es gibt Formeln, die fuer jede Zahl genau sagen, ob sie Primzahl ist oder nicht. Leider ist keine von denen "einfach", d.h. sie auszurechnen dauert fuer grosse Zahlen sehr lang. Wie gross sollen denn deine Zahlen sein, die du testen willst?

Fuer relativ kleine Zahlen reicht die Probedivision.
Fuer grosse Zahlen brauchst du andere Faktorisierungsverfahren.

Gruss,
SirJective
27.05.2004, 14:21 m00xi Auf diesen Beitrag antworten »

Es gibt ein netter Verfahren, welches sich Sieb des Eratosthenes nennt:

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

#include<iostream.h>
static const int N=1000;
int main()
{
   int i,a[N];
   for (i=2;i<N;i++) a[i]=1;
   for (i=2;i<N;i++)
      if (a[i])
         for (int j=i;j*i<N;j++)
            a[i*j]=0;
   for (i=2;i<N;i++)
      if (a[i]) cout << " " << i;
   cout << endl;
}


Das sucht dir ne Menge Primzahlen raus, kannst dir ja mal ansehen. Wenn du genau wissen willst, ob eine Zahl prim ist, dann schlag ich dir das vor *inseinenalgorithmenbüchernrumwühlt*.

...
Scheiss Bücher, ich find nix Augenzwinkern Aber hab was im Internet gefunden

hier eine Beschreibung.
27.05.2004, 14:41 Irrlicht Auf diesen Beitrag antworten »

@m00xi Dieses Verfahren reicht, wenn die Zahlen klein sind. Wenn die Zahlen gross sind, dann bekommst du Speicherplatzprobleme.
Wenn man nur daran interessiert ist, ob EINE vorgegebene Zahl prim ist, ist die Probedivision schneller.
27.05.2004, 14:46 Leopold Auf diesen Beitrag antworten »

Ich habe mit dem Sieb des Eratosthenes einmal mühelos die Primzahlen unterhalb von 10 Millionen berechnet. Dabei habe ich nicht ein Feld von Byte-Variablen angelegt, sondern ein Feld von Bits. Damit kann man ja immerhin den Speicherplatz verachtfachen. Danach wird es allerdings zugegebenermaßen eng.
27.05.2004, 14:47 m00xi Auf diesen Beitrag antworten »

Ah gute Idee, das kannst du eigentlich gleich mal an Robert Sedgewick schicken, da der Code eben aus seinem Buch war :-)

Danke
Gruß
Hanno
27.05.2004, 14:48 SirJective Auf diesen Beitrag antworten »

Ups, hab da was durcheinandergebracht. Zum Test der Primalitaet braucht man natuerlich nicht unbeding ein Faktorisierungsverfahren, sondern eher einen Primzahltest.

Aber wie gesagt, was sinnvoll ist, haengt von der Groesser der zu testenden Zahlen ab.

@m00xi: Um z.B. Primzahlen in der Groesse von einer Milliarde mit dem Sieb des Eratosthenes zu finden, brauchst du bei einfacher Darstellung (nur ungerade Zahlen bitweise) etwa 62MB Arbeitsspeicher fuer die Tabelle. (Ich habs bisher nur bis 300 Mio. gemacht.)

Um aber fuer eine vorgegebene Zahl dieser Groesse die Primalitaet zu testen, brauchst du hoechstens 16000 Test-Divisionen.
27.05.2004, 14:55 Ben Sisko Auf diesen Beitrag antworten »

Mal interessehalber: Hatte das einen bestimmten Grund, dass ihr das gemacht habt, außer eurem Interesse am Thema?

Edit: "Zweck" wäre ein passenderer Ausdruck gewesen.
27.05.2004, 15:34 Silver (Gast) Auf diesen Beitrag antworten »

Danke, aber irgendwie schaff ich das nicht! Das programm sagt mir zwar das 11 eine Primzahl ist aber es sagt mir auch das 25 eine Primzahl ist verwirrt !
27.05.2004, 15:37 m00xi Auf diesen Beitrag antworten »

Es tut mir leid, dass ich dich damit verwirrt habe. Das Sieb des Eratosthenes gibt dir alle Primzahlen von 1 bis N aus. Der angehängte Link war eine beschreibung für einen Algorithmus mit dem du auch für eine einzelne Zahl bestimmen kannst, ob sie Prim ist. Das ist es ja, was du wolltest. Das Sieb des Eratosthenes kann aber für Interessierte durchaus einen blick wert sein.

Gruß
Hanno
27.05.2004, 16:43 derHund Auf diesen Beitrag antworten »

Zitat:
Original von Leopold Dabei habe ich nicht ein Feld von Byte-Variablen angelegt, sondern ein Feld von Bits. Damit kann man ja immerhin den Speicherplatz verachtfachen.

[ot]nur interesse-halber: was hast du denn dann in den bit-variablen gespeichert?[/ot]
27.05.2004, 16:48 m00xi Auf diesen Beitrag antworten »

Ob eine Zahl prim ist oder nicht.
27.05.2004, 17:13 Poff Auf diesen Beitrag antworten »

... so ist es.

Nun du kannst dir doch einen Bereich von z.B Tausend Zahlen
als eine ununterbrochene Strecke von (durchnummerierten) Bit's
vorstellen. Wir das Bit gelöscht ist die zugehörige nicht prim ...

Die zugehörige Zahl (Stelle des Bits in der Kette) ergibt sich
später einfach durch 'Abzählen' ...

so in etwa ...


smile
27.05.2004, 17:14 Leopold Auf diesen Beitrag antworten »

Die Bits stehen für die Zahlen 1,2,3,... . Ist ein Bit 1, so ist die betreffende Zahl eine Primzahl, ist es 0, so ist die Zahl keine Primzahl.

Wenn der Algorithmus beginnt, ist das Bitfeld folgendermaßen initialisiert:
111111111111111111111111111...

Und wenn der Algorithmus durch ist, sieht das Bitfeld so aus:
01101010001010001010001000001010...

1: keine Primzahl
2: Primzahl
3: Primzahl
4: keine Primzahl

usw.
27.05.2004, 17:16 m00xi Auf diesen Beitrag antworten »

Schön, unter Programmierern zu sein *sichgleichvielwohlerfühlt* smile
27.05.2004, 17:32 Poff Auf diesen Beitrag antworten »

*gg*


smile
27.05.2004, 21:55 Irrlicht Auf diesen Beitrag antworten »

Und wie mein Freund schon sagte, kann man mit etwas Mehraufwand beim Zugriff den Speicherplatzbedarf halbieren, indem man nur die ungeraden Zahlen speichert. Dann erspart man sich den Wegstreich-Durchlauf mit der 2 und fängt direkt bei 3 an.
27.05.2004, 21:57 m00xi Auf diesen Beitrag antworten »

Gute Idee, meine Güte, der gute Sedgewick hat in seinem Büchlein einiges vergessen Augenzwinkern
27.05.2004, 22:02 Irrlicht Auf diesen Beitrag antworten »

Vielleicht wollte Sedgewick mit seinem Programmbeispiel aber nur zeigen, wie der Algorithmus funktioniert. Da ist noch kein Platz für jede einzelne Optimierung. Eine Optimierung, die in einem verbesserten Programm noch fehlt ist, mit der i-Schleife nur bis einschließlich zur (abgerundeten) Quadratwurzel von N zu gehen.
27.05.2004, 22:17 m00xi Auf diesen Beitrag antworten »

Es ist immerhin das Buch, in dem alles ausführlicher behandelt wird. Das ist der erste Teil der Aufteilung des Buches "Algorithemen". Eigneltich wird dort alles 100 mal durchgekaut und diskutiert, deshalb wundere ich mich.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Schulmathematik » Sonstiges » 1 = Primzahl ???