Sestavljeno število je število, ki ga lahko razcepimo na vsaj dve praštevili. Na primer, 15 = 3 × 5; 9 = 3 × 3; 12 = 2 × 2 × 3.

Imamo deset sestavljenih števil, manjših od trideset, ki jih lahko razcepimo na natanko dve, ne nujno različni, praštevili: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.

Koliko sestavljenih števil, manjših od 10⁸, lahko razcepimo na natanko dve ne nujno različni praštevili?

Torej napisati moramo funkcijo, ki izračuna, koliko sestavljenih števil manjših od nekega števila n, se da razcepiti na natanko dve ne nujno različni praštevili. Rešitev naloge nam bo dala funkcija, ki bo za parameter prejela n = 10⁸. Najprej torej napišemo algoritem za izračun za poljuben parameter n, nato na koncu vstavimo zahtevani n in če je algoritem pravilen dobimo rešitev.

Nalogo lahko rešimo tako, da napišemo dve funkciji in sicer: jePrastevilo (stevilo) in composites (n). Druga nam s pomočjo prve funkcije vrne iskano rešitev problema.

Ideja rešitve je v tem, da sestavimo dva seznama praštevil. V prvem seznamu bodo vsa praštevila, ki so manjša ali enaka kvadratnemu korenu parametra n (praštevila≤√n), v drugem seznamu pa bodo vsa praštevila, ki so manjša ali enaka polovici n-ja (praštevila ≤ n/2). Ta dva seznama sem izbrala zato, ker le kombinacija dveh praštevil iz teh dveh seznamov, nam lahko da produkt, ki je manjši od n. Če bi drugi seznam vseboval praštevila, ki so večja od n/2, potem bi bil produkt le teh praštevil s katerim koli drugim praštevilom definitivno večji od števila n. Nas pa zanimajo ravno taka sestavljena števila, ki jih lahko razcepimo na ne nujno različni dve praštevili, katerih produkt je manjši od n. Seznama sem sestavila s pomočjo funkcije jePrastevilo.

Nato sem definirala še nek števec, ki je štel koliko parov praštevil ustreza naslednjima pogojema:

• praštevilo1 <= praštevilo2 in
• praštevilo1 * praštevilo2 < n.

Pri tem pa upoštevamo, da jemljemo praštevila1 iz prvega seznama, praštevila2 pa iz drugega seznama. Če dvojica ustreza obema pogojema se števec poveča za 1. Ko pregledamo vse možne dvojice dobimo iskani rezultat, ki ga vrne funkcija composites.

def jePrastevilo(stevilo):
    assert type(stevilo) == int, "Parameter stevilo mora biti podano kot celo število."
    assert stevilo > 0, "Parameter stevilo mora biti pozitivno celo število."
    # Če je stevilo enako 1, potem ni praštevilo, zato vrnemo False.
    if stevilo == 1:
        return False
    # Če je stevilo enako 2, potem je praštevilo in vrnemo True.
    if stevilo == 2:
        return True
    # Če je stevilo sodo in je večje od 2, potem seveda ni praštevilo in zato vrnemo False.
    if stevilo > 2 and stevilo % 2 == 0:
        return False
    # Če je stevilo liho število večje od 2 in ima poleg sebe in števila 1 še katerega drugega delitelja,
    # potem seveda ni praštevilo in zato vrnemo False.
    for i in range(3, int(stevilo**0.5) + 2, 2):
        if stevilo % i == 0:
            return False
    # Če pridemo do sem, je stevilo res praštevilo in zato vrnemo True.
    return True

Funkcija jePrastevilo samo preveri, če je parameter stevilo praštevilo ali ne. Če je, nam vrne True, v nasprotnem primeru pa vrne False.

def composites (n):
    assert type(n) == int, "Parameter n mora biti podan kot celo število."
    assert n > 1, "Parameter n mora biti pozitivno celo število, večje od 1"
    # V seznam s1 shranimo vsa praštevila, ki so manjša ali enaka kvadratnemu korenu števila n. Pri tem si
    # pomagamo s funkcijo jePrastevilo.
    s1 = [i for i in range(2, int(n**0.5)+2) if jePrastevilo(i)]
    # V seznam s2 shranimo vsa praštevila, ki so manjša ali enaka številu n/2. Pri tem si pomagamo s funkcijo
    # jePrastevilo.
    s2 = [i for i in range(2, n//2 + 2) if jePrastevilo(i)]
    # Definiramo števec stevec, ki bo štel sestavljena števila, ki pri razcepu na prafaktorje razpadejo na
    # natanko dve ne nujno različni praštevili.
    stevec = 0
    # Z zanko for gremo po seznamu s1.
    for i in s1:
        # Z zanko for gremo po seznamu s2.
        for j in s2:
            # Če je element i seznama s1 <= elementu j seznama s2 (<= ker ni nujno da sta različni praštevili)
            # in i * j < n, potem stevec povečamo za 1.
            if i <= j and  i * j < n:
                stevec+=1
    # Vrnemo stevec.
    return stevec

Funkcija composites preveri koliko je sestavljenih števil manjših od vhodnega parametra n , ki ob razcepu na prafaktorje razpadejo na natanko dve ni nujno različni praštevili.

Torej definiramo dva seznama: s1 in s2 . V seznamu s1 so vsa praštevila manjša ali enaka kvadratnemu korenu števila n . V seznamu s2 pa so praštevila, ki so manjša ali enaka vrednosti n /2. Definiramo stevec , ki bo štel število parov praštevil iz obeh seznamov (po eno praštevilo iz vsakega seznama), ki ustrezajo pogojema:

• praštevilo1 <= praštevilo2 in
• praštevilo1 * praštevilo2 < n, kjer je praštevilo1 element seznama s1 , praštevilo2 pa element seznama s2 .

Ko se zanka zaključi samo še vrnemo stevec in imamo rešitev.

Pri funkciji jePrastevilo moramo preveriti naslednje:

• kaj se zgodi, če ji kot parameter podamo niz, seznam, decimalno število ali celo število, ki je manjše od 1.
• če funkcija vrača ustrezne logične vrednosti True in False, za določene primere.

Pri funkciji composites moramo preveriti naslednje:

• kaj se zgodi, če ji kot parameter podamo sezname, niz, decimalno število ali celo število, ki je manjše od 2.
• če funkcija vrača smiselne rezultate za majhne n in seveda če vrne pravo rešitev za naš primer, ko je n = 100000000.