Помимо простой реализации Сита Эратосфена с временной сложностью O (N log log N), я также пытался реализовать модификацию с временной сложностью O (N). Хотя оба результата дают желаемый результат, как-то раньше, чем раньше, требуется гораздо меньше времени по сравнению со следующим, и я не могу понять, почему. Я был бы очень признателен за некоторые советы по этому вопросу.
Реализация 1:
def build_sieve_eratosthenes(num):
## Creates sieve of size (num+1) to correct for 0-indexing.
primes_sieve = [1] * (num+1)
primes_sieve[0] = primes_sieve[1] = 0
for p in range(2, num):
if primes_sieve[p] == 1:
for mul in range(2*p, num+1, p):
primes_sieve[mul] = 0
return primes_sieve
Реализация 2:
def build_sieve_eratosthenes_linear(num):
## Creates sieve of size (num+1) to correct for 0-indexing.
primes_sieve = [1] * (num+1)
primes_sieve[0] = primes_sieve[1] = 0
## Builds a list of size (num+1) recording the smallest prime factor of each number.
SPF = [1] * (num+1)
## Builds a list of all primes seen so far with pos indicator of position where to insert the next prime.
## Uses a large fixed memory allocation scheme to avoid the usage of append list operation.
primes = [0] * num
pos = 0
for p in range(2, num+1):
if primes_sieve[p] == 1:
primes[pos] = p
pos = pos + 1
## Smallest prime factor of a prime is a prime itself.
SPF[p] = p
for i in range(0, pos):
if p * primes[i] <= num and primes[i] <= SPF[p]:
primes_sieve[p*primes[i]] = 0
SPF[p * primes[i]] = primes[i]
else:
break
return primes_sieve
test_num = 2000000
Метод испытания
def find_sum_of_primes_upto_num_with_sieve(sieve, num):
primes_sieve = sieve(num)
primes_sum = 0
for n in range(len(primes_sieve)):
if primes_sieve[n] == 1:
primes_sum = primes_sum + n
return primes_sum
Результаты:
start2 = time.time()
sum_2 = find_sum_of_primes_upto_num_with_sieve(build_sieve_eratosthenes, test_num)
end2 = time.time()
print("Sum of primes obtained: ", sum_2)
print("Time taken by checking primality of each number is %f sec" % (end2 - start2))
Сумма полученных простых чисел: 142913828922
Время, затраченное на проверку простоты каждого числа, составляет 0,647822 se c
start3 = time.time()
sum_3 = find_sum_of_primes_upto_num_with_sieve(build_sieve_eratosthenes_linear, test_num)
end3 = time.time()
print("Sum of primes obtained: ", sum_3)
print("Time taken by checking primality of each number is %f sec" % (end3 - start3))
Сумма полученных простых чисел: 142913828922
Время, затрачиваемое на проверку простоты каждого числа, составляет 1.561308 se c