Орлин обнови решението на 23.04.2012 15:53 (преди около 12 години)
+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