### Divisors, prime numbers
### =======================


### ---------------------------------------------------------------------------
### Exercise 1: Prime number?
###
### Decide whether a given natural number n is a prime number.
### (Don't use is_prime() or any other prime-related function of Sage.)

def is_prime_1 (n):
    pass #TODO
    #return True/False

def test1 ():
    print("1. Prime number?")
    for n in range(101):
        assert is_prime_1(n) == is_prime(n), f"is_prime_1({n})"
    print(is_prime_1(1237))
    #print(is_prime_1(1212121))
    #print(is_prime_1(1234567891))
    print()
#test1()


### ---------------------------------------------------------------------------
### Exercise 2: Twin prime pairs
###
### Two prime numbers whose distance is two is called a twin prime pair.
### Create the list of all twin prime pairs between 1 and n:
### [(3, 5), (5, 7), (11, 13), ...]. (Warning: don't exceed n with the primes!)

def twin_primes (n):
    pass #TODO

def test2():
    print("2. Twin prime pairs:")
    print(twin_primes(600))
    print()
#test2()


### ---------------------------------------------------------------------------
### Exercise 3: Sieve of Eratosthenes
###
### Create all prime numbers up to a given n using the sieve of Eratosthenes.
### (Don't use the built-in prime-related functions of Sage.)
### The function returns a list of bools, meaning whether the index is prime:
### [False, False, True, True, False, True, False, ...]
###    0      1      2     3     4      5     6

def eratosthenes (n):
    pass #TODO

def test3 ():
    print("3. Sieve of Eratosthenes:")
    P = eratosthenes(100)
    # Make the list of bools readable:
    if P:
        assert len(P) == 101, "there are 101 numbers between 0 and 100!"
        for i in range(len(P)):
            assert type(P[i]) == bool, f"P[{i}]={P[i]} is not bool"
            assert P[i] == is_prime(i), f"P[{i}]={P[i]}"
            if P[i]: print(i, end=" ")
        print()
    # Is it fast enough for big n?
    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()


### ---------------------------------------------------------------------------
### Exercise 4: Number of divisors
###

### a) Calculate τ(n) ("tau(n)") using the definition (see the PDF).
### (Don't use the mathematical functions of Sage.)
def tau_def (n):
    pass #TODO
    #return ...

### b) Calculate τ(n) ("tau(n)") using the prime factorization of n.
### (Here you can use the Sage function that creates the factorization.)
def tau_fac (n):
    pass #TODO

### c) Print those n's between 1 and 100 for which τ(n) ("tau(n)") is odd.
### What are these numbers? Why?
def odd_taus ():
    pass #TODO

def test4 ():
    print("4. Number of divisors:")
    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()


### ---------------------------------------------------------------------------
### Exercise 5: List of divisors
###
### Create the list of positive divisors of a given n (in increasing order).
### (Don't use the mathematical functions of Sage.)
### (All tests should run within a few seconds!)

def divisor_list (n):
    pass #TODO

def test5 ():
    print("5. List of divisors:")
    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()


### ---------------------------------------------------------------------------
### Exercise 6: Perfect numbers
###
### Print all perfect numbers up to 10000. (See the PDF for perfect numbers.)

def perfect_numbers ():
    pass #TODO

def test6 ():
    print("6. Perfect numbers:")
    perfect_numbers()
    print()
#test6()