def U27_1000W以內(nèi)的素數(shù)():
    import math
    import time

    def is_prime(num):
        if num == 2:
            return True
        if num <= 1 or num % 2 == 0:
            return False
        for div in range(3, int(math.sqrt(num) + 1), 2):
            if num % div == 0:
                return False
        return True

    def run_program(N):
        total = 0
        for i in range(N):
            if is_prime(i):
                total += 1
        return total

    # if __name__ == "__main__":
    N = 10000000
    start = time.time()
    total = run_program(N)
    end = time.time()
    print(f"1000萬以內(nèi)所有的素數(shù)有 {total} 個")
    print(f"純Python耗時： {end - start} 秒\b")
    return end - start

def U28_1000W以內(nèi)的素數(shù)_Numba裝飾器():
    import math
    import time
    from numba import njit, prange

    # @njit 相當于 @jit(nopython=True) 
    @njit
    def is_prime(num):
        if num == 2:        # 2為素數(shù)
            return True
        if num <= 1 or num % 2 == 0:     # 偶數(shù)中除了2都不是素數(shù)
            return False
        for div in range(3, int(math.sqrt(num) + 1), 2):
            if num % div == 0:
                return False
        return True

    #使用Numba的prange來進行并發(fā)循環(huán)計算
    @njit(parallel = True)
    def run_program(N):
        total = 0
        #使用Numba提供的prange參數(shù)來進行并行計算
        for i in prange(N):
            if is_prime(i):
                total += 1
        return total

    # if __name__ == "__main__":
    N = 10000000
    start = time.time()
    total = run_program(N)
    end = time.time()
    print(f"1000萬以內(nèi)所有的素數(shù)有 {total} 個")
    print(f"Numba裝飾器耗時： {end - start} 秒\b")
    return end - start

t0 = U27_1000W以內(nèi)的素數(shù)()
t1 = U28_1000W以內(nèi)的素數(shù)_Numba裝飾器()
print(f'使用numba裝飾器，速度提升 {round(t0/t1, 0)} 倍')


1000萬以內(nèi)所有的素數(shù)有 664579 個
純Python耗時： 86.78110885620117 秒
1000萬以內(nèi)所有的素數(shù)有 664579 個
Numba裝飾器耗時： 3.9410934448242188 秒
使用numba裝飾器，速度提升 22.0 倍

# 算法一：針對輸入的數(shù)字x，我們可以遍歷從2到x-1這個區(qū)間中的數(shù)，如果x能被這個區(qū)間中任意一個數(shù)整除，那么它就不是質(zhì)數(shù)。
def is_prime1(x):
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

# 算法二：對算法一的優(yōu)化，事實上只需要遍歷從2到√x即可。
def is_prime2(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True

# 算法三：偶數(shù)中除了2都不是質(zhì)數(shù)，且奇數(shù)的因數(shù)也沒有偶數(shù)，因此可以進一步優(yōu)化。
def is_prime3(x):
    if x == 2:
        return True
    elif x % 2 == 0:
        return False
    for i in range(3, int(x ** 0.5) + 1, 2):
        if x % i == 0:
            return False
    return True

# 算法四：任何一個自然數(shù)，總可以表示成以下六種形式之一：6n，6n+1，6n+2，6n+3，6n+4，6n+5（n=0,1,2...）我們可以發(fā)現(xiàn)，除了2和3，只有形如6n+1和6n+5的數(shù)有可能是質(zhì)數(shù)。且形如6n+1和6n+5的數(shù)如果不是質(zhì)數(shù)，它們的因數(shù)也會含有形如6n+1或者6n+5的數(shù)，因此可以得到如下算法：
def is_prime4(x):
    if (x == 2) or (x == 3):
        return True
    if (x % 6 != 1) and (x % 6 != 5):
        return False
    for i in range(5, int(x ** 0.5) + 1, 6):
        if (x % i == 0) or (x % (i + 2) == 0):
            return False
    return True