Решение на Генератори от Петко Пъдевски

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

Към профила на Петко Пъдевски

Резултати

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

Код

"""
Created on May 1, 2012
@author: ppadevski
"""
from bisect import bisect_left
from itertools import takewhile
from math import sqrt
_memory = [2]
def _ensure_primes(lower_limit):
"""
Ensures that there is a prime number ready to be picked by any generator.
@type lower_limit: C{int}
@param lower_limit: The lower limit of prime numbers to pre-generate.
@note: Modifies the cached _memory with primes.
"""
iterations = 1
while _memory[-1] < lower_limit:
n = _memory[-1] + iterations
success = True
upper_limit = sqrt(n)
for prime_number in takewhile(lambda x: x <= upper_limit, _memory):
if n % prime_number == 0:
success = False
break
if success:
_memory.append(n)
iterations += 1
return _memory
def _is_prime(number):
"""
Checks if the passed number is in fact a prime.
@pre: All primes lower or equal to the number are already found.
@type number: C{int}
@param number: The number to check.
@rtype: C{bool}
@return: True iff the number is prime, False otherwise
"""
pos = bisect_left(_memory, number)
return pos != len(_memory) and _memory[pos] == number
def primes():
"""
Creates a generator which iterates over prime numbers.
"""
n = 2
while True:
_ensure_primes(n)
if _is_prime(n):
yield n
n += 1
def semiprimes():
"""
Creates a generator which iterates over semi-prime numbers
@note: A semi-prime number is a number that is a result of the
multiplication of two prime numbers.
"""
n = 2
while True:
prime_numbers = _ensure_primes(n / 2)
upper_limit = sqrt(n)
for p in takewhile(lambda x: x <= upper_limit, prime_numbers):
if n % p == 0 and _is_prime(n / p):
yield n
break
n += 1

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

....
----------------------------------------------------------------------
Ran 4 tests in 0.009s

OK

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

Петко обнови решението на 01.05.2012 13:34 (преди над 8 години)

+"""
+Created on May 1, 2012
+
+@author: ppadevski
+"""
+from bisect import bisect_left
+from itertools import takewhile
+from math import sqrt
+
+_memory = [2]
+
+def _ensure_primes(lower_limit):
+ """
+ Ensures that there is a prime number ready to be picked by any generator.
+
+ @type lower_limit: C{int}
+ @param lower_limit: The lower limit of prime numbers to pre-generate.
+
+ @note: Modifies the cached _memory with primes.
+ """
+ iterations = 1
+ while _memory[-1] < lower_limit:
+ n = _memory[-1] + iterations
+ success = True
+
+ upper_limit = sqrt(n)
+ for prime_number in takewhile(lambda x: x <= upper_limit, _memory):
+ if n % prime_number == 0:
+ success = False
+ break
+
+ if success:
+ _memory.append(n)
+ iterations += 1
+
+ return _memory
+
+def _is_prime(number):
+ """
+ Checks if the passed number is in fact a prime.
+ @pre: All primes lower or equal to the number are already found.
+
+ @type number: C{int}
+ @param number: The number to check.
+
+ @rtype: C{bool}
+ @return: True iff the number is prime, False otherwise
+ """
+ pos = bisect_left(_memory, number)
+ return pos != len(_memory) and _memory[pos] == number
+
+def primes():
+ """
+ Creates a generator which iterates over prime numbers.
+ """
+ n = 2
+ while True:
+ _ensure_primes(n)
+
+ if _is_prime(n):
+ yield n
+
+ n += 1
+
+def semiprimes():
+ """
+ Creates a generator which iterates over semi-prime numbers
+
+ @note: A semi-prime number is a number that is a result of the
+ multiplication of two prime numbers.
+ """
+ n = 2
+ while True:
+ prime_numbers = _ensure_primes(n / 2)
+
+ upper_limit = sqrt(n)
+ for p in takewhile(lambda x: x <= upper_limit, prime_numbers):
+ if n % p == 0 and _is_prime(n / p):
+ yield n
+ break
+
+ n += 1