判断素数函数及输出不大于该数的所有素数

描述

写一个函数isPrime(n)用于判断一个数字n是不是素数，用户输入一个正整数，在一行内输出不大于该数的所有素数，各数后面用一个空格分隔。

输入格式

输入一个正整数

输出格式

不大于该数的所有素数，各数后面用一个空格分隔。

输入输出示例

 解析：

    素数的概念又称为质数，一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数。

    可以定义一个函数，传入一个整数，返回其是否为素数。判定一个数是否为素数的方法是，用传入的整数 n 除从2到n-1之间的每一个整数，如果存在某个可以整除的数，则其不是素数，如果没有任何除1和其本身以外的因子，则其是素数。(时间复杂度为o(n))

# 将判断一个整数 n 是否为素数的代码定义为一个函数isPrime(n)# 传入参数为整数 n，n 是素数时返回值为True，否则返回False# 时间复杂度为o(n)def isPrime(n):  # 判断参数 n 是否为素数的函数    if n <= 1:   # 小于2的数字都不是素数        return False    for i in range(2,n):   # 根据素数定义判定是否是素数，是素数返回1        if n % i == 0:     # 从 2到n-1中如果存在一个数是i，使n 可以整除i，则n不是素数            return False    else:                  # 若for循环未遇到return正常结束，则n是素数        return True# 以下代码调用定义的isPrime()判定num是否为素数，输出小于m的所有素数m = int(input())               # 输入一个正整数for num in range(m):           # 获得小于m的整数数列    if isPrime(num):           # 如果isPrime(num)返回值为True,num 是素数        print(num,end = ' ')   # 输出num# 输入 100# 输出 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

    其主程序部分可以修改为以下模式，使当前文件可以做为模块被其他程序调用。当文件直接被运行时，if __name__ == "__main__":语句后的语句块中的输入输出等语句会被执行。当文件被当做模块import时，只调用其中的函数，if __name__ == "__main__":后的语句块不会被执行。

# 将判断一个整数 n 是否为素数的代码定义为一个函数isPrime(n)# 传入参数为整数 n，n 是素数时返回值为True，否则返回False# 时间复杂度为o(n)def isPrime(n):  # 判断参数 n 是否为素数的函数    if n <= 1:   # 小于2的数字都不是素数        return False    for i in range(2,n):   # 根据素数定义判定是否是素数，是素数返回1        if n % i == 0:     # 从 2到n-1中如果存在一个数是i，使n 可以整除i，则n不是素数            return False    else:                  # 若for循环未遇到return正常结束，则n是素数        return True# __name__ 是当前模块名，当模块被直接运行时模块名为 __main__ 。# 当模块被直接运行时，以下代码块将被运行，当模块是被导入时，代码块不被运行。# 可以删除if __name__ == "__main__":，将下面语句块向前提一级# 以下代码调用定义的isPrime()判定num是否为素数，输出小于m的所有素数if __name__ == "__main__":    m = int(input())       # 输入一个正整数    for num in range(m):   # 获得小于m的整数数列        if isPrime(num):   # 如果isPrime(num)返回值为True,num 是素数            print(num,end = ' ')     # 输出num# 输入 100# 输出 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

    我们知道一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，所以对于每个数n，并不需要从2判断到n-1，遍历到sqrt(n)即可。因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数。这样可以显著提升算法的效率，上面判断素数函数可以修改为：

# 传入参数为整数 n，n 是素数时返回值为True，否则返回False# 时间复杂度为o(n)def isPrime(n):  # 判断参数 n 是否为素数的函数    if n <= 1:   # 小于2的数字都不是素数        return False    for i in range(2,n):   # 根据素数定义判定是否是素数，是素数返回1        if n % i == 0:     # 从 2到n-1中如果存在一个数是i，使n 可以整除i，则n不是素数            return False    else:                  # 若for循环未遇到return正常结束，则n是素数        return True

  依据经验，我们知道素数分布的规律，除了2以外的所有素数都是奇数，所以可以只判定奇数是否是素数就可以，可以减少一半的判定素数的计算量。

if __name__ == "__main__":    m = int(input())       # 输入一个正整数    if m > 2:        print(2,end = ' ')    for num in range(3,m,2): # 获得小于m的整数数列        if isPrime(num):     # 如果isPrime(num)返回值为True,num 是素数            print(num,end = ' ')     # 输出num

    素数分布的规律：大于等于5的素数一定和6的倍数相邻。例如5和7，11和13,17和19等等。

查看100以内的素数：

2 3   5 7    11 13    17 19    23    29 31    37    41 43    47 53    59 61   67    71 73    79 83 89 97

   可以发现除2和3外，其他数都是6的倍数的相邻数：

6-1，6+1，2*6-1，2*6+1，3*6-1，3*6+1...

    但要注意，6 的倍数的相邻数并不全是素数，例如35。所以还是需要调用素数判定函数进行判定。只判定6的倍数的相邻数是否是素数就可以找到所有素数。这样可以进一步减少判定的次数，提高效率。注意2和3要单独判定。

if __name__ == "__main__":    m = int(input())       # 输入一个正整数    if m > 2:        print(2,end = ' ')    if m > 3:        print(3,end = ' ')    for num in range(0,m,6):   # 获得小于m的整数数列        if isPrime(num - 1):   # 如果isPrime(num -1)返回值为True,num 是素数            print(num - 1,end = ' ')     # 输出num - 1        if isPrime(num + 1):   # 如果isPrime(num + 1)返回值为True,num 是素数            print(num + 1,end = ' ')     # 输出num + 1

       综合以上分析，可以同时优先判定素数的函数和判定的代码：

def isPrime(n):  # 判断参数 n 是否为素数的函数    if n <= 1:      # 小于2的数字都不是素数        return False    for i in range(2,int(n ** 0.5) + 1):   # 两因子相同时，为保证取到右边界，需加1    # for i in range(2,int(math.sqrt(n)) + 1)        if n % i == 0:     # 从 2到n-1中如果存在一个数是i，使n 可以整除i，则n不是素数            return False    else:                  # 若for循环未遇到return正常结束，则n是素数        return Trueif __name__ == "__main__":    m = int(input())       # 输入一个正整数    if m > 2:        print(2,end = ' ')    if m > 3:        print(3,end = ' ')    for num in range(0,m,6):   # 获得小于m的整数数列        if isPrime(num - 1):   # 如果isPrime(num -1)返回值为True,num 是素数            print(num - 1,end = ' ')     # 输出num - 1        if isPrime(num + 1):   # 如果isPrime(num + 1)返回值为True,num 是素数            print(num + 1,end = ' ')     # 输出num + 1

        除了这些方法以外，还可以使用筛选法，先生成小于n的所有数字，再把 2 到 sqrt(n) 之间的整数的倍数依次去掉，剩余的就是小于n的所有素数了。这种方法的效率更高

(注：此图片来自网络，版权归原作者所有，此处仅用于教学演示)

def isprime(n):  '''筛选法获取小于n的所有素数'''  ls = list(range(3, n, 2))          # 待判断整数  for index in range(int(n ** 0.5)): # 最大整数的平方根    current = ls[index]    if current > int(n ** 0.5): # 如果当前数字已大于最大整数的平方根，结束判断      break    # 对该位置之后的元素进行过滤    ls[index + 1:] = list(filter(lambda x: 0 if not x%current else x,ls[index + 1:]))  return [2] + ls   # 2是素数，单独加上去# 输出100以内所有素数 print(*isprime(100))