Христо обнови решението на 29.04.2012 01:03 (преди над 12 години)
+"""
+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