www.Primzahlen.de

Primzahltests

Sieb des Eratosthenes*


Einfache Prinzipdarstellung Komplexe Darstellung

Einfache Prinzipdarstellung

Dieses funktioniert nach folgendem Prinzip:

Schreibt man eine Liste aller natürlichen Zahlen auf, die man überprüfen will, dann sieht das nachher z.B. so aus:


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

a) Nun streicht man als erstes die 1 weg, da es sich bei 1 um keine Primzahl handelt.

b) Es folgt die 2. 2 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 2 als Primzahl.

c) Wir streichen nun alle durch 2 teilbaren Zahlen, weil diese nicht Primzahlen sein können. (Sie hätten jeweils die Teiler 1,2 und sich selbst)

d) Die 3 ist nun die nächste ungestrichene Zahl! Wir markieren 3 als Primzahl.

e) Wir streichen nun alle durch 3 teilbaren Zahlen, weil diese ebenfalls keine Primzahlen mehr sein können.

f) Nun wiederholen wir Schritt d) und e) bis alle Zahlen entweder als Primzahlen markiert, bzw. als Nichtprimzahlen durchgestrichen sind.
Achtung: Diese Schritte müssen nur bis zur Zahl durchgeführt werden, die größer oder gleich der Wurzel des zu überprüfenden Bereich ist. z.B. 10 bei 100, 32 bei 1000, da 10 * 10 = 100 bzw. 32 * 32 = 1024 > 1000

Man erhält in dem oberen Beispiel nun eine Liste von Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.


nach oben



Komplexe Darstellung


Schreibt man eine Liste aller natürlichen Zahlen auf, die man überprüfen will. Hier im Beispiel bis 660.

Achtung: Diese Schritte müssen nur bis zur Zahl durchgeführt werden, die größer oder gleich der Wurzel des zu überprüfenden Bereiches ist. Z.B. 10 bei 100, 32 bei 1000, da 10 * 10 = 100 bzw. 32 * 32 = 1024 > 1000. Hier bei 660 bis 26.

Nun streicht man als erstes die 1 weg, da es sich bei 1 um keine Primzahl handelt.
Es folgt die 2. Die Zahl 2 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 2 als Primzahl und streichen nun alle durch 2 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 2. Sie liegen alle auf Geraden.

Komplexe Darstellung mit 2

Es folgt die 3. Die Zahl 3 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 3 als Primzahl und streichen nun alle durch 3 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 3. Sie liegen alle auf Geraden.

Komplexe Darstellung mit 3

Es werden nur ungestrichene Zahlen beachtet.

Es folgt die 5. Die Zahl 5 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 5 als Primzahl und streichen nun alle durch 5 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 5. Sie liegen alle auf Geraden.

Komplexe Darstellung mit 5

Es werden nur ungestrichene Zahlen beachtet.

Es folgt die 7. Die Zahl 7 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 7 als Primzahl und streichen nun alle durch 7 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 7. Sie liegen alle auf Geraden.

Komplexe Darstellung mit 7

Es werden nur ungestrichene Zahlen beachtet.

Es folgt die 11. Die Zahl 11 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 11 als Primzahl und streichen nun alle durch 11 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 11. Sie liegen alle auf Geraden.

Komplexe Darstellung mit 11

Es werden nur ungestrichene Zahlen beachtet.

Es folgt die 13. Die Zahl 13 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 13 als Primzahl und streichen nun alle durch 13 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 13. Sie liegen alle auf Geraden.

Komplexe Darstellung mit 13

Es werden nur ungestrichene Zahlen beachtet.

Es folgt die 17. Die Zahl 17 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 17 als Primzahl und streichen nun alle durch 17 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 17. Sie liegen alle auf Geraden.

Komplexe Darstellung mit 17

Es werden nur ungestrichene Zahlen beachtet.

Es folgt die 19. Die Zahl 19 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 19 als Primzahl und streichen nun alle durch 19 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 19. Sie liegen alle auf Geraden.

Komplexe Darstellung mit 19

Es werden nur ungestrichene Zahlen beachtet.

Es folgt die 23. Die Zahl 23 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 23 als Primzahl und streichen nun alle durch 23 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 23. Sie liegen alle auf Geraden.

Komplexe Darstellung mit 23

Die Zahlen 24, 25 und 26 sind schon gestrichen. Jetzt ist das Ziel erreicht. Alle noch nicht gestrichenen Zahlen sind Primzahlen (siehe oben).

Wir markieren die restlichen Zahlen als Primzahlen.



nach oben



* griechischer Gelehrter und Dichter aus Kyrene, * um 275 v. Chr., † um 195 v. Chr.; Leiter der Bibliothek von Alexandria, bezeichnete sich als Erster als Philologe; er berechnete annähernd richtig den Umfang der Erdkugel aus den Sonnenhöhen an 2 Punkten des gleichen Meridians und entwarf eine Erdkarte; erzählende Gedichte: "Hermes", "Erigone". (Quelle: www.wissen.de)