eratosthenovo sito

In [2]:
tabulka = list(range(21))
In [4]:
tabulka = [ 0 for _ in range(21)]
In [5]:
tabulka #0- nema delitela, inac najmensi delitel, vzynam ma od 2
Out[5]:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
In [7]:
# vyskrtame delitele 2, teda zapiseme si tam dvojku
cislo = 2
hodnota = cislo*2
while hodnota < len(tabulka):
    if tabulka[hodnota] == 0:
        tabulka[hodnota] = cislo
    hodnota += cislo
In [8]:
tabulka
Out[8]:
[0, 0, 0, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2]
In [9]:
# vyskrtame delitele 2, teda zapiseme si tam dvojku
cislo = 3
hodnota = cislo*2
while hodnota < len(tabulka):
    if tabulka[hodnota] == 0:
        tabulka[hodnota] = cislo
    hodnota += cislo
tabulka
Out[9]:
[0, 0, 0, 0, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2]
In [10]:
tabulka[6]
Out[10]:
2
In [16]:
n = 100
tabulka = [ 0 for _ in range(n+1)]
for cislo in range(2, n+1):
    if tabulka[cislo] == 0:
        hodnota = cislo*2
        while hodnota < len(tabulka):
            if tabulka[hodnota] == 0:
                tabulka[hodnota] = cislo
            hodnota += cislo
tabulka
Out[16]:
[0,
 0,
 0,
 0,
 2,
 0,
 2,
 0,
 2,
 3,
 2,
 0,
 2,
 0,
 2,
 3,
 2,
 0,
 2,
 0,
 2,
 3,
 2,
 0,
 2,
 5,
 2,
 3,
 2,
 0,
 2,
 0,
 2,
 3,
 2,
 5,
 2,
 0,
 2,
 3,
 2,
 0,
 2,
 0,
 2,
 3,
 2,
 0,
 2,
 7,
 2,
 3,
 2,
 0,
 2,
 5,
 2,
 3,
 2,
 0,
 2,
 0,
 2,
 3,
 2,
 5,
 2,
 0,
 2,
 3,
 2,
 0,
 2,
 0,
 2,
 3,
 2,
 7,
 2,
 0,
 2,
 3,
 2,
 0,
 2,
 5,
 2,
 3,
 2,
 0,
 2,
 7,
 2,
 3,
 2,
 5,
 2,
 0,
 2,
 3,
 2]
In [17]:
for i in range(2, n):
    print(f'{i}: {tabulka[i]}' if tabulka[i] > 0 else f'{i} je prvocislo')

2 je prvocislo
3 je prvocislo
4: 2
5 je prvocislo
6: 2
7 je prvocislo
8: 2
9: 3
10: 2
11 je prvocislo
12: 2
13 je prvocislo
14: 2
15: 3
16: 2
17 je prvocislo
18: 2
19 je prvocislo
20: 2
21: 3
22: 2
23 je prvocislo
24: 2
25: 5
26: 2
27: 3
28: 2
29 je prvocislo
30: 2
31 je prvocislo
32: 2
33: 3
34: 2
35: 5
36: 2
37 je prvocislo
38: 2
39: 3
40: 2
41 je prvocislo
42: 2
43 je prvocislo
44: 2
45: 3
46: 2
47 je prvocislo
48: 2
49: 7
50: 2
51: 3
52: 2
53 je prvocislo
54: 2
55: 5
56: 2
57: 3
58: 2
59 je prvocislo
60: 2
61 je prvocislo
62: 2
63: 3
64: 2
65: 5
66: 2
67 je prvocislo
68: 2
69: 3
70: 2
71 je prvocislo
72: 2
73 je prvocislo
74: 2
75: 3
76: 2
77: 7
78: 2
79 je prvocislo
80: 2
81: 3
82: 2
83 je prvocislo
84: 2
85: 5
86: 2
87: 3
88: 2
89 je prvocislo
90: 2
91: 7
92: 2
93: 3
94: 2
95: 5
96: 2
97 je prvocislo
98: 2
99: 3
In [22]:
print(*[i for i, hodnota in enumerate(tabulka) if hodnota == 0 and i > 1])

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
In [ ]: