import random, itertools


# Sieve of Eratosthenes algorithm
def sieve():
    D = {}
    yield 2
    for q in itertools.islice(itertools.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q * q] = q
            yield q
        else:
            x = p + q
            while x in D or not (x & 1):
                x += p
            D[x] = p


# Creates a list of prime numbers up to the given argument
def get_primes_sieve(n):
    return list(itertools.takewhile(lambda p: p < n, sieve()))


def get_semiprime(n):
    primes = get_primes_sieve(n)
    l = len(primes)
    p = primes[random.randrange(l)]
    q = primes[random.randrange(l)]
    return p * q


N = get_semiprime(1000000000)

print("semiprime N =", N)

# Test
# 2888947
# 8158357
# 35624893
# 42459479
# 102584047
# 225149933
# 6607016917
# 6299969561
# 4074339571
# 417901915699

# RSA-768 768-bit
# 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

# RSA-2048 2048-bit  Bron: http://ospkibook.sourceforge.net/docs/OSPKI-2.4.7/OSPKI-html/sample-key-components.htm
# 27928727520532098560054510086934803266769027328779773633517624932519959782855440353509062663825852727223986298676726328202776042265127475116423330432277935745868052617793594651686619933029730312573799176384081348734718092523534765500572439819131028990684498563888859874177855756336652257804467879680080859571614665706994859343608810676186674067708949755093039975941211253008157978789036441127011095726560212571370863346201690633153889542846093941923225064368851460069960392982454529684837005125465003797310139479221307918200583851065828489354285517184240655579549337386740031302249496379882799360098372401884741329801
