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

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

Към профила на Христо Георгиев

Резултати

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

Код

"""
Notice:
The generators are not the best approach for receiving prime numbers.
The only reason to be used is that the limit between prime numbers must be received is unknown.
If it is known, then building a sieve is much faster
One reason is that the generator uses slow number division and square root arithmetic,
while the sieve uses the faster boolean and memory access arithmetic
The same is valid for semiprimes, which could be gathered while building the sieve, and then sorted
"""
from math import *
def get_primes(limit):
"""
Build list of primes numbers below and including limit
Time speed: 2.75 sec for primes bellow 2 million
"""
sieve = [True for x in range(2, limit + 3)]
for i in range(2,len(sieve)):
if sieve[i]:
for j in range(2, len(sieve)):
number = i * j
if number > limit: break
sieve[number] = False
result = []
for x in range(2, len(sieve)):
if sieve[x]: result.append(x)
return result
primeNumbers = get_primes(1000)
def is_prime(number):
"""
Test if a given number is prime.
Uses a global list of prime numbers primeNumbers, which are initially populated
with some of the first primes, and then populated in run time.
This means that it uses dynamical optimisation
"""
if number in primeNumbers: return True
sqrtRootNumber = floor(sqrt(number))+1
for x in primeNumbers:
if x > sqrtRootNumber: break
if number % x == 0: return False
for x in range(2, sqrtRootNumber+1):
if number % x == 0: return False
primeNumbers.append(number)
return True
def is_semiprime(number):
"""
Test if a number is a semiprime.
"""
if is_prime(number): return False
sqrtRootNumber = floor(sqrt(number))+1
for p in primeNumbers:
if p > sqrtRootNumber: break
if number % p == 0:
if is_prime(number / p):
return True
return False
def primes():
"""
Generator function that yeilds the prime numbers in incereasing order
Use as:
>>> primes = primes()
>>> print(next(primes)) #print 2
>>> print(next(primes)) #print 3
>>> print(next(primes)) #print 5
....
"""
yield 2
number = 3
while True:
if is_prime(number): yield number
number +=1
def semiprimes():
"""
Generator function that yeilds the semiprime numbers in incereasing order
This are the numbers product of two prime numbers
Use as:
>>> semiprimes = semiprimes()
>>> print(next(semiprimes)) #print 4
>>> print(next(semiprimes)) #print 6
>>> print(next(semiprimes)) #print 9
....
"""
number = 2
while True:
if is_semiprime(number): yield number
number +=1

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

....
----------------------------------------------------------------------
Ran 4 tests in 0.029s

OK

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

Христо обнови решението на 29.04.2012 01:03 (преди над 8 години)

+"""
+Notice:
+The generators are not the best approach for receiving prime numbers.
+
+The only reason to be used is that the limit between prime numbers must be received is unknown.
+If it is known, then building a sieve is much faster
+
+One reason is that the generator uses slow number division and square root arithmetic,
+while the sieve uses the faster boolean and memory access arithmetic
+
+The same is valid for semiprimes, which could be gathered while building the sieve, and then sorted
+"""
+from math import *
+
+def get_primes(limit):
+ """
+ Build list of primes numbers below and including limit
+
+ Time speed: 2.75 sec for primes bellow 2 million
+ """
+ sieve = [True for x in range(2, limit + 3)]
+ for i in range(2,len(sieve)):
+ if sieve[i]:
+ for j in range(2, len(sieve)):
+ number = i * j
+ if number > limit: break
+ sieve[number] = False
+
+ result = []
+ for x in range(2, len(sieve)):
+ if sieve[x]: result.append(x)
+
+ return result
+primeNumbers = get_primes(1000)
+
+def is_prime(number):
+ """
+ Test if a given number is prime.
+
+ Uses a global list of prime numbers primeNumbers, which are initially populated
+ with some of the first primes, and then populated in run time.
+
+ This means that it uses dynamical optimisation
+ """
+
+ if number in primeNumbers: return True
+
+ sqrtRootNumber = floor(sqrt(number))+1
+ for x in primeNumbers:
+ if x > sqrtRootNumber: break
+ if number % x == 0: return False
+ for x in range(2, sqrtRootNumber+1):
+ if number % x == 0: return False
+
+ primeNumbers.append(number)
+ return True
+
+def is_semiprime(number):
+ """
+ Test if a number is a semiprime.
+ """
+ if is_prime(number): return False
+
+ sqrtRootNumber = floor(sqrt(number))+1
+ for p in primeNumbers:
+ if p > sqrtRootNumber: break
+ if number % p == 0:
+ if is_prime(number / p):
+ return True
+ return False
+
+def primes():
+ """
+ Generator function that yeilds the prime numbers in incereasing order
+ Use as:
+ >>> primes = primes()
+ >>> print(next(primes)) #print 2
+ >>> print(next(primes)) #print 3
+ >>> print(next(primes)) #print 5
+ ....
+ """
+
+ yield 2
+ number = 3
+ while True:
+ if is_prime(number): yield number
+ number +=1
+
+def semiprimes():
+ """
+ Generator function that yeilds the semiprime numbers in incereasing order
+ This are the numbers product of two prime numbers
+
+ Use as:
+ >>> semiprimes = semiprimes()
+ >>> print(next(semiprimes)) #print 4
+ >>> print(next(semiprimes)) #print 6
+ >>> print(next(semiprimes)) #print 9
+ ....
+ """
+ number = 2
+ while True:
+ if is_semiprime(number): yield number
+ number +=1