10-я проблема в проекте Эйлера:Project Euler 10 - Почему первый код на Python работает намного быстрее, чем второй?
Сумма простых чисел ниже 10 составляет 2 + 3 + 5 + 7 = 17.
Найти сумму всех простых чисел меньше двух миллионов.
Я нашел этот фрагмент кода:
sieve = [True] * 2000000 # Sieve is faster for 2M primes
def mark(sieve, x):
for i in xrange(x+x, len(sieve), x):
sieve[i] = False
for x in xrange(2, int(len(sieve) ** 0.5) + 1):
if sieve[x]: mark(sieve, x)
print sum(i for i in xrange(2, len(sieve)) if sieve[i])
опубликован here , которые проходят в течение 3 секунд.
Я написал этот код:
def isprime(n):
for x in xrange(3, int(n**0.5)+1):
if n % x == 0:
return False
return True
sum=0;
for i in xrange(1,int(2e6),2):
if isprime(i):
sum += i
Я не понимаю, почему мой код (второй) гораздо медленнее?
Почему это O (n log logn), является n = log (2e6) или n = 2e6? – 0x90
Я имею в виду 'n = 2e6' –
Пробное деление останавливается у квадратного корня, поэтому его сложность лучше, чем O (n^2), с верхней части головы, я бы сказал O (n^1.5/log n), но я не учитывал композиты с большими наименьшими основными факторами, поэтому он может быть немного хуже (верхняя граница O (n^1.5)). –