题目 6: 求解100以内的所有素数

描述

输出100以内的所有素数，素数之间以一个空格区分

第一种解法 暴力遍历法

solve

def prime(n):
    '''
    傻瓜法
    '''
    prime = []
    for i in range(2, n+1):
        if is_prime(i):
            prime.append(i)
    return prime
    
def is_prime(n):
    if n == 2:
        return True
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

第2种解法 将素数判断的遍历长度缩减到 sqrt(n)

def prime(n):
    '''
    sqrt n 法
    '''
    prime = []
    for i in range(2, n+1):
        if is_prime(i):
            prime.append(i)
    return prime
            
def is_prime(n):
    if n == 2:
        return True
    for i in range(2, floor(sqrt(n))+1):
        if n % i == 0:
            return False
    return True

第3种方法 埃拉托斯特尼筛法

def prime_3(n):
    '''
    普通筛法 埃拉托斯特尼筛法
    '''
    check = np.ones(n+1)
    prime = []
    for i in range(2, n+1):
        if check[i]:
            prime.append(i)
            # 此循环也可以和上层 if 并列 但这样效率高一些
            for j in range(2*i, n+1, i):
                check[j] = 0
    return prime

第4种方法 线性筛法 欧拉筛法

def prime_4(n):
    '''
    线性筛法 欧拉筛法
    '''
    check = np.ones(n+1)
    prime = []
    tot = 0
    for i in range(2, n+1):
        if check[i]:
            prime.append(i)
            tot += 1
        for j in range(tot):
            if i * prime[j] > n:
                break
            check[i * prime[j]] = 0
            if i % prime[j] == 0:
                break
    return prime