### Oszthatóság, prímszámok
### =======================


### ---------------------------------------------------------------------------
### 1. feladat: Prímszám-e
###
### Döntsük el, hogy egy adott n természetes szám prímszám-e.
### (Ne használjuk a Sage is_prime() vagy egyéb prímszámos függvényeit.)

def is_prime_1 (n):
    if n < 2: return False
    for k in range(2, n):  # 2-től n-1-ig
    	if n % k == 0:
    		return False
    return True

def is_prime_2 (n):
    if n < 2: return False
    for k in range(2, n//2 + 1):  # 2-től n/2-ig
    	if n % k == 0:
    		return False
    return True

def is_prime_3 (n):
    if n < 2: return False
    for k in range(2, floor(sqrt(n)) + 1):  # 2-től gyök n-ig
    	if n % k == 0:
    		return False
    return True

def is_prime_4 (n):
    if n < 2: return False
    k = 2
    while k*k <= n:
    	if n % k == 0:
    		return False
    	k += 1
    return True

def test1 ():
    print("1. Prímszám-e:")
    for n in range(101):
        assert is_prime_1(n) == is_prime(n), f"is_prime_1({n})"
        assert is_prime_2(n) == is_prime(n), f"is_prime_2({n})"
        assert is_prime_3(n) == is_prime(n), f"is_prime_3({n})"
        assert is_prime_4(n) == is_prime(n), f"is_prime_3({n})"
    print(is_prime_1(1237))
    print(is_prime_2(1212121))
    print(is_prime_4(1234567891))
    print()
test1()


### ---------------------------------------------------------------------------
### 2. feladat: Ikerprímpárok
###
### Ikerprímpárnak nevezünk két prímszámot, ha a távolságuk kettő.
### Hozzunk létre egy listát az 1 és n közötti ikerprímpárokkal:
### [(3, 5), (5, 7), (11, 13), ...]. (Vigyázat: ne legyen n-nél nagyobb szám!)

def twin_primes (n):
    pass #TODO

def test2():
    print("2. Ikerprímpárok:")
    print(twin_primes(600))
    print()
#test2()


### ---------------------------------------------------------------------------
### 3. feladat: Eratoszthenész szitája
###
### Állítsuk elő adott n-ig az összes prímszámot Eratoszthenész szitájával.
### (Ne használjuk a Sage beépített prímszámos függvényeit.)
### A függvény visszatérési értéke egy bool-lista, hogy az index prímszám-e:
### [False, False, True, True, False, True, False, ...]
###    0      1      2     3     4      5     6

def eratosthenes (n):
    pass #TODO

def test3 ():
    print("3. Eratoszthenész szitája:")
    P = eratosthenes(100)
    # A bool-lista olvashatóvá alakítása:
    if P:
        assert len(P) == 101, "0-tól 100-ig 101 szám van!"
        for i in range(len(P)):
            assert type(P[i]) == bool, f"P[{i}]={P[i]} nem bool"
            assert P[i] == is_prime(i), f"P[{i}]={P[i]}"
            if P[i]: print(i, end=" ")
        print()
    # Nagy n-re is elég gyors?
    n = 100000
    P = eratosthenes(n)
    if P:
        i = len(P) - 1
        while not P[i]: i -= 1
        assert i == previous_prime(n)
        print(n, "OK")
    print()
#test3()


### ---------------------------------------------------------------------------
### 4. feladat: Osztók száma
###

### a) Számítsuk ki τ(n)-et ("tau(n)") a definíció alapján (lásd a jegyzetet).
### (Ne használjuk a Sage matematikai függvényeit.)
def tau_def (n):
    pass #TODO
    #return ...

### b) Számítsuk ki τ(n)-et ("tau(n)") a prímtényezős felbontás alapján.
### (Itt használhatjuk a felbontást előállító Sage függvényt.)
def tau_fac (n):
    pass #TODO

### c) Írassuk ki 1-től 100-ig azokat az n-eket, amelyekre τ(n) ("tau(n)")
### páratlan. Mely számokat kapjuk meg? Vajon miért?
def odd_taus ():
    pass #TODO

def test4 ():
    print("4. Osztók száma:")
    if tau_def(2) != None:
        for n in range(1, 101):
            assert tau_def(n) == number_of_divisors(n), f"tau_def({n})"
        print("tau_def() OK")
    if tau_fac(2) != None:
        for n in range(1, 1001):
            assert tau_fac(n) == number_of_divisors(n), f"tau_fac({n})"
        print("tau_fac() OK")
    odd_taus()
    print()
#test4()


### ---------------------------------------------------------------------------
### 5. feladat: Osztók listája
###
### Adjuk vissza az adott n pozitív osztóit egy listában (növekvő sorrendben).
### (Ne használjuk a Sage matematikai függvényeit.)
### (Minden teszt fusson le pár másodpercen belül!)

def divisor_list (n):
    pass #TODO

def test5 ():
    print("5. Osztók listája:")
    for n in range(1, 101):
        assert divisor_list(n) == divisors(n), f"divisor_list({n})"
    print(1000, ":", divisor_list(1000))
    print(1111111, ":", divisor_list(1111111))
    print(2^30, ":", divisor_list(2^30))
    print()
#test5()


### ---------------------------------------------------------------------------
### 6. feladat: Tökéletes számok
###
### Írjuk ki az összes tökéletes számot 10000-ig. (Lásd a jegyzetet.)

def perfect_numbers ():
    pass #TODO

def test6 ():
    print("6. Tökéletes számok:")
    perfect_numbers()
    print()
#test6()