-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSiebDesEratosthenes.Rmd
134 lines (82 loc) · 3.95 KB
/
SiebDesEratosthenes.Rmd
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
---
title:
output:
html_document:
code_folding: show
---
```{r setup, include=FALSE, message=FALSE, warning=FALSE}
knitr::opts_chunk$set(echo = TRUE)
# library(reticulate)
# use_python("C:\\Users\gschleifer\AppData\Local\Microsoft\WindowsApps\python.exe")
```
<br>
# __Sieb des Eratosthenes__ {.tabset .tabset-pills}
<br>
# Primzahlen {.active}
<br>
## Eine Primzahl ist:
<br>
- <p><span style="font-size:1.5em">Eine __natürliche Zahl__:</span></p>
- <p><span style="font-size:1.2em">grösser als 1</span></p>
- <p><span style="font-size:1.2em">nur zwei Teiler: 1 und die Zahl selbst</span></p>
- <p><span style="font-size:1.5em">Kann nicht als Produkt von zwei kleineren Integers kalkuliert werden</span></p>
- <p><span style="font-size:1.5em">Die Zahlen, die keine Primzahlen sind, heißen zusammengesetzte Zahlen</span></p>
<p><span style="font-size:1.5em"> ......... </span></p>
<br>
- Negative Zahlen sind keine Primzahlen
- Mit Ausnahme der __1__ ist jede natürliche Zahl entweder eine Primzahl oder zusammengesetzt.
# Bedeutung
<br>
#### Kryptography/Verschlüsselung
- Primfaktoren finden ist extrem rechenintensiv
- RSA Verschlüsselung
- Sicherheit im Internet
- Asymetrische Verschlüsselung (public vs private keys)
## __Algorithmus-Sieb von Eratosthenes__
<br>
- <p><span style="font-size:1.5em">Liste `2 bis n` wird erstellt (1 $\neq$ Primzahl)</span></p>
- <p><span style="font-size:1.5em">Wir beginnen mit `x == 2`, da dies die kleinste und erste Primzahl ist</span></p>
- <p><span style="font-size:1.5em">Die zusammengesetzten/vielfachen Zahlen der 2 werden "gesiebt"</span></p>
- <p><span style="font-size:1.5em">Nächste Primzahl oder die kleinste nicht markierte Zahl wird gewählt</span></p>
- <p><span style="font-size:1.5em">Die zusammengesetzten == vielfachen dieser Zahl (`x == 3`) werden "gesiebt"</span></p>
- <p><span style="font-size:1.5em">Iteration bis der Wert von `x` kleiner oder gleich der $\sqrt{n}$</span></p>
Hinweis: Die mathematische Begründung ist recht einfach. Der Zahlenbereich n kann faktorisiert werden als
n=a*b
Auch hier ist n =Algorithmus-Sieb von Eratosthenes*Algorithmus-Sieb von Eratosthenes
= (Faktor kleiner als Algorithmus-Sieb von Eratosthenes) * (Faktor größer als Sieb des Eratosthenes-Algorithmus)
Also mindestens einer der Primfaktoren oder beide müssen <= seinAlgorithmus-Sieb von Eratosthenes. Also Überquerung zu Algorithmus-Sieb von Eratosthenes wird genug sein.
Schritt 5) Nach diesen vier Schritten wären die verbleibenden nicht markierten Zahlen alle Primzahlen in dem gegebenen Bereich n.
## __Bedeutung der Primzahlen__
* Verschlüsselung (RSA)
* private keys in der Kryptowelt
- e.g. eliptic curve cryptography
* Viele Primzahlen Muster vorhanden (z.B. bei Primzahlzwillingen)
<br>
<br>
# Pseudocode
<br>
```{r, engine = 'bash', eval = FALSE}
algorithm Sieve of Eratosthenes is
input: an integer n > 1.
output: all prime numbers from 2 through n.
let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., not exceeding √n do
if A[i] is true
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
set A[j] := false
return all i such that A[i] is true.
```
1. Die kleinste Primzahl wird ausgewählt und alle Vielfachen davon herausgefiltert
- Der Prozess läuft in einer Schleife für den deffinierten Bereich
* Der Filtervorgang beginnt mit der kleinsten Primzahl. Eine Primzahl ist eine natürliche Zahl, die größer als 1 ist und nur zwei Teiler hat, nämlich 1 und die Zahl selbst. Die Zahlen, die keine Primzahlen sind, heißen zusammengesetzte Zahlen.
* unordered list
+ sub-item 1
+ sub-item 2
- sub-sub-item 1
# Skript
```{r, echo = TRUE, results='markup'}
input <- c(1:100) ; input
```