

In [ ]:

    
%autosave 0

Programming hands on

習うより慣れろ！(narau yori narero) more practice, less learning; practice makes perfect.

a + b

input: each line contains 2 integer output: print sum of the 2 integer

input: input_ab.txt, output: standard out

sample input:
1 1
100 150
123 321
11112222 22223333

sample output:
2
250
444
33335555



In [ ]:

    
# write answer

a+b modified (1)

Add grand total at the end of line.

input: input_ab.txt, output: standard out

sample input:
1 1
100 150
123 321
11112222 22223333

sample output:
2
250
444
33335555
33336251



In [ ]:

a+b modified (2)

input: each line contains 1 or more integer output: print sum of the input, and grand total

input: inputab3.txt, output: standard out

sample input:
1
1 2 3
123 321
10 9 8 7 6 5 4 3 2 1

sample output:
1
6
444
55
506



In [ ]:

a+b modified (3)

input: each line contains 1 or more integer output: print sum of the input. Grand Total, Average, Minimum of line total, Maximum of line total

Use round() function for average.

input: inputab3.txt, output: standard out

sample input:
1
1 2 3
123 321
10 9 8 7 6 5 4 3 2 1

sample output:
1
6
444
55
Grand Total: 506 Average: 126.5 Min: 1 Max: 444



In [ ]:

Prime numbers (1)

print all prime numbers below 100 (2 3 5 7 .... 97) (hint: Sieve of Eratosthenes)

The definition of Prime Number is that it can be divided only 1 and itself. (see is_prime_not_efficient() function below. But in order to check if the number $N$ is prime or not, it's not necessary to check up to $N-1$, but the prime number equal or less of $\sqrt{N}$, because if N is a product of $A$ and $B$, one of the divider is equal or less than $\sqrt{N}$.

Definition-1: Prime number is a integer bigger than 1 and can be divided only by 1 and itself
Definition-2: Composite Number is a integer bigger than 1, and not Prime number (i.e. has more than 1 divider except 1 and itself)
Definition-3: Prime Number is not Composit number
Definition-4: Composite Number can be factorized. If a number is a composite number, it is a product of smaller Prime numbers.
Definition-5: Every integer bigger than 1 is either Prime or Composite number

Premise-1: Composite Number has a divider of Prime number equal or less than $\sqrt{N}$
Conclusion: If $N$ can not be divided by the integer eqaul or less than $\sqrt{N}$, it's Prime number

Proof of Premise-1:

If N is a Composite Number (Non-Prime-Number) and product of positive integer A and B, and if A is smaller or equal to B, then A is smaller or equal to $\sqrt{N}$ $$(N = A \cdot B) \\ (1 \lt A \le B \lt N) \rightarrow (A \le \sqrt{N})$$

If $A$ is bigger than $\sqrt{N}$, then $A \cdot B \gt N$. Let's assume that $$A = \sqrt{N} + a \\ B = \sqrt{N} + b \\ 0 \lt a \le b$$ Then $$A \cdot B \\ = (\sqrt{N} + a)(\sqrt{N} + b) \\ = (\sqrt{N}^2 + (a+b)\sqrt{N} + a \cdot b) \gt N$$



In [ ]:

    
def is_prime_not_efficient(n):
    if n < 2: return False
    for div in range(2,n):
        if n % div == 0:
            return False  # not Prime
    return True

print(2, is_prime_not_efficient(2))
print(97, is_prime_not_efficient(97))
print(1000000, is_prime_not_efficient(1000000))
print(1000003, is_prime_not_efficient(1000003))



In [ ]:

    
#!/usr/bin/python3
# -*- coding: utf-8 -*-

'''
find prime numbers up to MAX_NUMBER
sieve of Eratosthenes
'''


MAX_NUMBER = 100

prime = [True for i in range(MAX_NUMBER+1)]
prime[0] = False   # 0 is not prime
prime[1] = False   # 1 is not prime

sqrt_max = int(MAX_NUMBER ** 0.5)  # check up to root(MAX_NUMBER)

for i in range(2, sqrt_max + 1):
    if prime[i]:
        for n in range(i+i, MAX_NUMBER+1, i):
            prime[n] = False

num_prime = 0
for i in range(MAX_NUMBER):
    if prime[i]:
        num_prime += 1
        print(i, end=' ')
# print(num_prime, 'prime number found under', MAX_NUMBER)

Prime number (2)

write a function, which takes 1 parameter (n), and returns n-th prime number.

example: n=1 output=2, n=2 output=3, n=3 output=5, n=5 output=11

nth_primt(10)



In [ ]:

    
#!/usr/bin/python3
# -*- coding: utf-8 -*-

'''
find N-th prime number
'''

prime = [2, 3]

def is_prime(candidate):
    sqrt_c = int(candidate ** 0.5)

    for p in prime:
        if p > sqrt_c:
            return True
        if candidate % p == 0:
            return False    # Not Prime number
    return True

def nth_prime(n):
    if not isinstance(n, int):
        raise TypeError
    if n < 1:
        raise ValueError
    prime_list_len = len(prime)
    if n <= prime_list_len:
        print('Prime List cache hit', prime_list_len)
        return prime[n-1]

    candidate = prime[-1]
    while prime_list_len < n:
        candidate += 2
        if is_prime(candidate):
             candidate += 2 prime.append(candidate)
            prime_list_len += 1

    return prime[-1]



In [ ]:

    
print(nth_prime(5))
print(nth_prime(100))
print(nth_prime(25))