# -*- coding: utf-8 -*-
"""
Spyder Editor

Python scripts file related with prime
"""

import math
import time

primeList=[]

# 用到math库中的开平方函数sqrt
def isprime1(num):
    if num <= 1:
        return False
    for i in range(2, int(math.sqrt(num))+1):   #也可以用num**0.5
        if num % i == 0:
            return False
        
    return True

# 没有使用math.sqrt函数，采用 i递增，保证i*i小于n作为判断条件
def isprime2(n):   # do not use math.sqrt
    if n <= 1:
        return False
    
    i = 1
    while i*i <= n:
        if n % i == 0:
            return False
        i += 1

    return True

# 不同math.sqrt， 首先判断是否是除2以外的偶数，再采用 i*i 小于n这个条件，递增i
def isprime(n):  
    """
    质数判断函数，不用sqrt（）函数，改用乘方代替开方，首先排除偶数
    do not use math.sqrt and delete even number
    """
    if n < 2 :           return False
    if n == 2 :         return True
    if n % 2 == 0 :   return False
   
    i = 3
    while i*i <= n:
        if n % i == 0:
            return False
        i += 2    # 偶数已经排除了，只判断奇数
    
    return True

    """有一段也可以用下列代替：
    for i in range(3,int(n**0.5)+1,2 ):
        if n % i == 0: return False
    """
# 最笨的但是最可以理解的求质数的方法，两重循环，注意break的应用。
def prime_number1(upper):
    prime_number = 0
    for n in range(2,upper):
        for x in range(2,n):
            if n % x == 0:
                #print("= = = * =" % (n,x,n/x ))
                break
        else:
            #print("= is a prime" % n)
            primeList.append(n)
            #prime_number += 1
    
    return primeList    #prime_number

#用math中的函数sqrt，大大降低循环次数，提高程序运行效率
def prime_number2(upper):
    prime_number = 0
    for n in range(2,upper):
        for x in range(2,int(math.sqrt(n))+1):   # or int(n**0.5)+1
            if n % x == 0:
                #print("= = = * =" % (n,x,n/x ))
                break
        else:
            #print("= is a prime" % n)
            #primeList.append(n)
            prime_number += 1
    
    return prime_number

#利用优化的质数判断函数isprime, 得到小于upper的质数个数
def prime_count(upper): # get prime count which less than the given upper
    primes = 0
    if upper <= 1:
        return 0
    for n in range(2,upper):
        if isprime(n):
            primes += 1
    return primes

#得到指定范围内的所有质数列表，范围[lower, upper), 一开一闭区间的所有质数列表
def prime_list(lower,upper):
    """
    input: [lower,upper)
    output: all primes between lower and upper, >=lower and < upper.
    """
    
    save_list = []
    for x in range(lower,upper):
        if isprime(x):
            save_list.append(x)
    
    return save_list

#测试程序
# Test data
max = [1000,10000,100000,1000000]

"""
Test function isprime(n) and prime_number(upper)
"""
"""
for upper in max:
    start_time = time.time()
    pn = prime_number(upper)
    end_time = time.time()
    spend_time = end_time - start_time
    print("estimated %f seconds" % (spend_time))