-
Notifications
You must be signed in to change notification settings - Fork 0
/
34 - prime_numbers_speed_test.py
56 lines (35 loc) · 1.85 KB
/
34 - prime_numbers_speed_test.py
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
import math, time
def main():
print("Замер скорости Решета Эратосфена против наивного улучшенного алгоритма, поиск простых чисел в диапазоне от 2 до 5e6.")
max_number = 5 * 10 ** 6 # Если вы долго ожидаете завершения, лучше снизить данное значение.
time_a = time.time()
list_soe = prime_soe(max_number)
time_b = time.time()
time_c = time.time()
list_prime = list(filter(is_prime_number, range(2, max_number + 1))) # Тоже самое, что проверять в цикле, разница на уровне погрешности.
time_d = time.time()
print(f"Время выполнения Решета Эратосфена = {(time_b - time_a):.5f} секунд.")
print(f"Время выполнения наивного улучшенного алгоритма = {(time_d - time_c):.5f} секунд.")
def prime_soe(max_number):
sieve = [True] * (max_number + 1)
sieve[0:2] = [False, False]
max_sqrt = math.floor(math.sqrt(max_number))
for number in range(2, max_sqrt + 1):
if sieve[number]:
for multiple in range(number * number, max_number + 1, number):
if multiple % number == 0: sieve[multiple] = False
prime_numbers = []
for index in range(0, len(sieve)):
if sieve[index]:
prime_numbers.append(index)
return prime_numbers
def is_prime_number(number):
if number < 2: return False
if number == 2: return True
if number % 2 == 0: return False
max_number = math.floor(math.sqrt(number))
for divider in range(3, max_number + 1, 2):
if number % divider == 0:
return False
return True
main()