算法-求n内的所有质数

时间:2021-06-04 11:03:00

筛选法-实现语言:python

#!/usr/bin/python
# -*- coding:UTF-8 -*-
#筛选出n内所有的素数
def getAllPrimeNum(n):
    #判断n是否大于3,否则直接输出n;
    if n <= 3:
        print "最大的素数就是:->",n
        return n;
    #第一步确定该次需要用来筛选的对象个数i,i*i=n;
    #第二步根据i个参数进行筛选,去除,留下的即为所求;
    listNum = [];
    #组装所有的数进列表方便筛选
    for i in range(1,n+1):
        listNum.append(i)
    print "listNum:->",listNum
    i = 1
    while (i * i <= n):
        i += 1
        for num in listNum:
            if (num%i) == 0:
                listNum.remove(num)
    print "最终获得在",n,"以内所有的素数为:",listNum
#检验一下函数
getAllPrimeNum(1000)