<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Prime number checking (is_prime() function)
The definition of Prime Number is that it can be divided only 1 and itself. (see is_prime_simple() 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 divisor is equal or less than $\sqrt{N}$.
Definition-1
Step1:  Java version (checking divisor from 2 to n-1)
```
class prime0 {
// is_prime() function, simple and slow version
static boolean is_prime(int n) {
    if (n &lt; 2) return false ;
    for (int div=2; div&lt;n; div++) {
        if (n % div == 0) return false ;
    }
    return true ;
}
public static void main(String argv[]) {
    for (int n = 0; n&lt;=100; n++) {
        if (is_prime(n)) System.out.printf("%d ", n) ;
    }
}
}
```
Step2:  Java version (checking up to square root of given number)
```
class prime1 {
// is_prime() function, faster version
static boolean is_prime(int n) {
    if (n &lt; 2) return false ;
    int sqrt_n = (int)Math.sqrt((double)n) ;
    // System.err.printf("n
Step3:  Prime numbers (1)
print all prime numbers below 100 (2 3 5 7 .... 97)  (hint
Step4:  Java sample code of Sieve of Eratosthenes
```
import java.util.List ;
import java.util.ArrayList ;
class sieve {
// sieve of Eratosthenes, find the prime numbers below given integer
static List&lt;Integer&gt; sieve(int n) {
    List&lt;Integer&gt; primes = new ArrayList&lt;&gt;() ;
    boolean is_prime[] = new boolean[n+1] ;
    for (int i=0; i&lt;=n; i++) is_prime[i] = true ;
    is_prime[0] = is_prime[1] = false ;
    for (int p=2; p&lt;=n; p++) {
        if (is_prime[p]) {
            for (int mop = p*2; mop&lt;=n; mop += p) {
                is_prime[mop] = false ;
            }
        }
    }
    for (int p=2; p&lt;=n; p++) {
        if (is_prime[p]) primes.add(p) ;
    }
    return primes ;
}
public static void main(String argv[]) {
    List&lt;Integer&gt; primes = sieve(100) ;
    for (int n
Step5:  Prime number (2)
write a function, which takes 1 parameter (n), and returns n-th prime number.
example
<ASSISTANT_TASK:>
Python Code:
def is_prime_simple(n):
    if n < 2: return False
    for div in range(2,n):
        if n % div == 0:
            return False  # not Prime
    return True
BIG_PRIME = 10**8 + 7
print(2, is_prime_simple(2))
print(97, is_prime_simple(97))
print(BIG_PRIME, is_prime_simple(BIG_PRIME))
Explanation: Prime number checking (is_prime() function)
The definition of Prime Number is that it can be divided only 1 and itself. (see is_prime_simple() 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 divisor 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 divisor 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 $N$ has a divisor equal or less than $\sqrt{N}$
Conclusion: If $N$ does not have divisor eqaul or less than $\sqrt{N}$, it's not Composite Number -> $N$ is Prime number
Premise-2: If $N$ has divisor of composite number $A$, divisor of $A$ is divisor of $N$. ( $N = A \cdot B, A= X \cdot Y \rightarrow N=X \cdot Y \cdot B$ )
From Definition-4 and Premise-2, we can conclude that it's necessary to check only prime number as a condidate of divisor 
Proof of Premise-1:
If N is a Composite Number (Non-Prime-Number) and product of positive integer(bigger than 1) 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$$
End of explanation
def is_prime_efficient(n):
    if n < 2: return False
    sqrt_n = int(n**0.5)
    for div in range(2,sqrt_n+1):
        if n % div == 0:
            print('Divisor=', div, end=' ')
            return False  # not Prime
    return True
BIG_PRIME = 10**8 + 7
print(2, is_prime_efficient(2))
print(49, is_prime_efficient(49))
print(97, is_prime_efficient(97))
print(BIG_PRIME, is_prime_efficient(BIG_PRIME))
Explanation: Java version (checking divisor from 2 to n-1)
```
class prime0 {
// is_prime() function, simple and slow version
static boolean is_prime(int n) {
    if (n &lt; 2) return false ;
    for (int div=2; div&lt;n; div++) {
        if (n % div == 0) return false ;
    }
    return true ;
}
public static void main(String argv[]) {
    for (int n = 0; n&lt;=100; n++) {
        if (is_prime(n)) System.out.printf("%d ", n) ;
    }
}
}
```
End of explanation
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
import math
MIN_NUM = 2
MAX_NUM = 100
def is_prime_simple(n):
    for i in range(2, n):  # 2 to n-1
        if n % i == 0:
            print(n, 'is devided by', i, 'log(i,base-n)', math.log(i,n))
            return False
    return True
for i in range(MIN_NUM, MAX_NUM+1):
    if is_prime_simple(i):
        print(i, 'is prime number')
Explanation: Java version (checking up to square root of given number)
```
class prime1 {
// is_prime() function, faster version
static boolean is_prime(int n) {
    if (n &lt; 2) return false ;
    int sqrt_n = (int)Math.sqrt((double)n) ;
    // System.err.printf("n: %d sqrt: %d\n", n, sqrt_n) ;
    for (int div=2; div&lt;=sqrt_n; div++) {
        if (n % div == 0) return false ;
    }
    return true ;
}
public static void main(String argv[]) {
    for (int n = 0; n&lt;=100; n++) {
        if (is_prime(n)) System.out.printf("%d ", n) ;
    }
}
}
```
Verification
Following test code shows that the log(divisor-of-N, base-N) does not exceed 0.5 (Square Root)
End of explanation
#!/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 mop in range(i+i, MAX_NUMBER+1, i):  # multiply of prime
            # Mark the multiples of the prime to False in the table
            prime[mop] = 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)
Explanation: Prime numbers (1)
print all prime numbers below 100 (2 3 5 7 .... 97)  (hint: Sieve of Eratosthenes)
End of explanation
#!/usr/bin/python3
# -*- coding: utf-8 -*-
'''
find prime numbers up to MAX_NUMBER
sieve of Eratosthenes
'''
# Same as above program, but faster
MAX_NUMBER = 100
# Mark Odd number as True, Even number as False
prime = [True if i & 1 else False for i in range(MAX_NUMBER+1)]
# prime = [False, True, False, True, False, True, ....]
# prime[0] = False   # 0 is not prime
prime[1] = False   # 1 is not prime
prime[2] = True    # 2 is prime
sqrt_max = int(MAX_NUMBER ** 0.5)  # check up to root(MAX_NUMBER)
for i in range(3, sqrt_max + 1):  # Only check odd number
    if prime[i]:
        for mop in range(i*3, MAX_NUMBER+1, i+i):  # ignore even number
            # Mark the multiples of the prime to False in the table
            prime[mop] = 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)
Explanation: Java sample code of Sieve of Eratosthenes
```
import java.util.List ;
import java.util.ArrayList ;
class sieve {
// sieve of Eratosthenes, find the prime numbers below given integer
static List&lt;Integer&gt; sieve(int n) {
    List&lt;Integer&gt; primes = new ArrayList&lt;&gt;() ;
    boolean is_prime[] = new boolean[n+1] ;
    for (int i=0; i&lt;=n; i++) is_prime[i] = true ;
    is_prime[0] = is_prime[1] = false ;
    for (int p=2; p&lt;=n; p++) {
        if (is_prime[p]) {
            for (int mop = p*2; mop&lt;=n; mop += p) {
                is_prime[mop] = false ;
            }
        }
    }
    for (int p=2; p&lt;=n; p++) {
        if (is_prime[p]) primes.add(p) ;
    }
    return primes ;
}
public static void main(String argv[]) {
    List&lt;Integer&gt; primes = sieve(100) ;
    for (int n: primes) {
        System.out.printf("%d ", n) ;
    }
}
}
```
Performance inprovement
2 is the only number that is prime and even. Above program can be improved if even number is properly handled.
End of explanation
#!/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]
print(nth_prime(5))
print(nth_prime(100))
print(nth_prime(25))
Explanation: 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_prime(10)
End of explanation
<END_TASK>