Решение на Генератори от Орлин Христов

Обратно към всички решения

Към профила на Орлин Христов

Резултати

  • 6 точки от тестове
  • 0 бонус точки
  • 6 точки общо
  • 4 успешни тест(а)
  • 0 неуспешни тест(а)

Код

def primes():
store = [2]
yield 2
number = 3
while True:
max_ = _isqrt(number)
for factor in store:
if number % factor:
if factor > max_:
store.append(number)
yield number
break
else:
break
number += 2
def _isqrt(n):
guess = (n >> n.bit_length() // 2) + 1
result = (guess + n // guess) // 2
while abs(result - guess) > 1:
guess = result
result = (guess + n // guess) // 2
while result * result > n:
result -= 1
return result
def semiprimes():
p_generator = primes()
p_store = {0: next(p_generator)} # stores sequence of prime numbers
p_id = 1 # the number of the next prime number
factors = {2: 1} # stores factors for a semiprime with key <= value
generated = {4} # stores semiprimes in the interval (2*P(n), 2*P(n+1)]
border = 4 # end of current interval
number = 3
while 1:
number += 1
if number in generated:
generated.remove(number)
yield number
if number == border:
p_store[p_id] = next(p_generator)
factors[p_store[p_id]] = p_id
border = 2 * p_store[p_id]
p_id += 1
for prime in p_store.values():
while factors[prime] < p_id:
candidate = prime * p_store[factors[prime]]
if candidate > border:
break
generated.add(candidate)
factors[prime] += 1

Лог от изпълнението

....
----------------------------------------------------------------------
Ran 4 tests in 0.004s

OK

История (1 версия и 0 коментара)

Орлин обнови решението на 23.04.2012 15:53 (преди над 8 години)

+def primes():
+ store = [2]
+ yield 2
+ number = 3
+ while True:
+ max_ = _isqrt(number)
+ for factor in store:
+ if number % factor:
+ if factor > max_:
+ store.append(number)
+ yield number
+ break
+ else:
+ break
+ number += 2
+
+
+def _isqrt(n):
+ guess = (n >> n.bit_length() // 2) + 1
+ result = (guess + n // guess) // 2
+ while abs(result - guess) > 1:
+ guess = result
+ result = (guess + n // guess) // 2
+ while result * result > n:
+ result -= 1
+ return result
+
+
+def semiprimes():
+ p_generator = primes()
+ p_store = {0: next(p_generator)} # stores sequence of prime numbers
+ p_id = 1 # the number of the next prime number
+ factors = {2: 1} # stores factors for a semiprime with key <= value
+ generated = {4} # stores semiprimes in the interval (2*P(n), 2*P(n+1)]
+ border = 4 # end of current interval
+
+ number = 3
+ while 1:
+ number += 1
+ if number in generated:
+ generated.remove(number)
+ yield number
+ if number == border:
+ p_store[p_id] = next(p_generator)
+ factors[p_store[p_id]] = p_id
+ border = 2 * p_store[p_id]
+ p_id += 1
+
+ for prime in p_store.values():
+ while factors[prime] < p_id:
+ candidate = prime * p_store[factors[prime]]
+ if candidate > border:
+ break
+ generated.add(candidate)
+ factors[prime] += 1