Python：每日一题 205

冬雪雪冬

我们的玩法做了一下改变：

1. 楼主不再提供答案。
2. 请大家先独立思考，再参考其他鱼油的解答，这样才有助于自己编程水平的提高。开始阶段是看不到其他人的回帖的，等答题完成，开始评分时再取消限制。
3. 鼓励大家积极答题，奖励的期限为出题后24小时内。
4. 根据答案的质量给予1~3鱼币的奖励。

题目：
本题又是求素数（质数）的题目，这回采用筛法来计算。关于筛法的原理，这里引用了百度百科的一段话：

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。

看看大家谁的程序更简单，更快捷。
为了简便就求出200以内的素数。

凌九霄

本代码中，最耗时的是sorted排序，占整个运行时间的54%左右。

import timeit

P  = '''
nums = [ x for x in range(2, 10000) ]
for i in range(len(nums)):
    if i < len(nums):
        nums = sorted(list(set(nums) - set([ nums[ i ] * x for x in range(2, nums[-1]//nums[i] + 1) ])))
    else:
        print(nums)
        break
'''
print('运行时间：',timeit.timeit(stmt=P,number=1))

塔利班

def fun205(n):
    r=[]
    f=list(range(2,n+1))
    while f:
        r.append(f.pop(0))
        f=[x  for x in f if x%r[-1]]
    return r

拉了盏灯

我这个还是有点慢，参考大神的程序，

def p(n):
    l = [i for i in range(2,n+1) if i==2 or i%2!=0]
    for i in range(3,n,2):
        if i in l:
            for i in (i for i in range(2*i,n,i) if i in l):
                l.remove(i)
    return l

Legend丶Hu

a = []
for i in range(100):
    a.append(i)

for i in range(2,51):
    if a[i]:
        j = i + i
        while j < 100:
            a[j] = 0
            j+=i
for i in range(2,100):
    if a[i]:
        print(a[i],end = " ")

靳泽宇

for x in range(1, 200):
    for i in range(2, x):  # ------------------从2开始一直除到它自身的前一个数
        if x % i == 0:  # ---------------------如果有余数为零，跳出循环
            break
    else:  # ----------------------------------全部除完没有余数为零的话，输出这个数字
        if x != 1:
            print(x)

黑白、

def odd_number():
    num = 1
    while True:
        num = num + 2
        yield num
def screen(num):
    return lambda x: x % num > 0
def fun205():
        yield 2
        temp = odd_number()
        while True:
            num = next(temp)
            yield num
            temp = filter(screen(num),temp)

numMAX = int(input('输入最大范围:'))
for each in fun205():
    if each < numMAX:
        print(each)
    else:
        break

子沙

def fun_205(x):
    list1=list(range(2,x+1))
    for i in list1:
        flag=0
        for j in range(2,i//2+1):
            if i%j==0:
                flag=1
        if flag==0:
            for k in range(2,x//i+1):
                if k*i in list1:
                    list1.remove(k*i)
    print(' ',*list1)
fun_205(200)

在东边

def primes(num):
    it = iter(range(2, num + 1))
    n = next(it)
    while n <= num:
        yield n
        it = filter(lambda x, n=n: x % n, it)
        n = next(it)

print(', '.join(map(str, primes(200))))

zhou995287902

import time
def isPrime(num):
    if num<2:
        return False
    else:
        for i in range(2,num//2+1):
            if num % i==0:
                return False
        else: 
            return True
def fun205(num):
    index=0
    while index<len(num):
        if isPrime(num[index]):
            for i in num[index+1:]:
                if i%num[index]==0:
                    num.remove(i)
        else:
            num.remove(num[index])
        index+=1
    print(num)

t1=time.time()
nums=[]
for i in range(2,201):
    nums.append(i)

fun205(nums)
print('耗时：',time.time()-t1)

久疤K

>>> def fun( n = 200 ):
        ns = list(range(n+1))
        ns[0:2] = [0,0]
        for i in range(n):
                if not ns[i]:
                        continue
                ns[i+i::i] = [0] * len(ns[i+i::i])
        return [x for x in ns if x]

>>> fun()
[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
>>> 

JessiFly

def fun205(n):
    primefilter = [x for x in range(2,n+1)]
    primes = []
    while primefilter:
        min_p = primefilter.pop(0)
        primes.append(min_p)
        i = min_p
        while i <= (n//min_p):
            mul_p = min_p * i
            if mul_p in primefilter:
                primefilter.remove(mul_p)
            i += 1
    for each in primes:
        print(each,end=' ')

if __name__ == '__main__':
    fun205(200)

archlzy

import math

def q205(num):
    temp = list(range(2, num+1))
    temp_bool = [True] * len(temp)
    for i in range(2, int(math.sqrt(num)) + 1):
        for j in range(2, num // i+1):
            if temp_bool[temp.index(i*j)] != False:
                temp_bool[temp.index(i*j)] = False
    return [temp[i] for i in range(len(temp_bool)) if temp_bool[i]]

天圆突破

def func205(n):
    collection, result = list(range(2, n+1)), []
    while collection:
        result.append(collection[0])
        collection = list(filter(lambda x:x%result[-1], collection[1:]))
    return result
    
if __name__ == '__main__':
    print(func205(400))

晓屁屁

x = [i for i in range(2,200)]
for i in x[:]:
    for y in range(2,200):
        z = i * y
        try:
            x.remove(z)
        except ValueError:
            pass
print(x)

chongchuigu

def a205(n):
    list1=[]
    for i in range(2,n+1):
        list1.append(i)
    list2=list1[:]
    for i in list1[0:n//2+1]:
        j=2
        if i not in list2:
            continue
        else:
            s=i*j
            while s<=n:                
                if s in list2:
                    list2.remove(s)
                j+=1
                s=i*j
    return list2
print(a205(2000))
            

绝境凤凰

啊啊啊啊啊啊啊啊啊啊a

祥哥威武

def getNumber(x):
    list0 = list((i for i in range(2, x+1)))
    for i in list0[:]:
        for j in list0[:]:
            if j <= i:
                continue
            if j % i == 0:
                list0.remove(j)
    return list0
print(getNumber(30))

claws0n

尝试了 5 个版本，没问题
200 测不出时间

import time

n = 2000

## code 1
start_time = time.time()

prime = []
check = []
k = int(n**0.5)
for i in range(3,n+1,2):
    if i not in check:
        prime.append(i)
        check.append(i)
        if i <= k:
            while check[-1] < n:
                check.append(check[-1]+i+i)
if n > 1:
    prime.insert(0,2)
elapsed_time1 = ( time.time() - start_time )*1000



## code 2
start_time = time.time()

prime2 = [i for i in range(3, n+1, 2)]
if n > 1:
    prime2.insert(0,2)
k = int(n**0.5)
for i in range(3,k+1,2):
    j = i
    while j < n - i:
        j += i+i
        try:
            prime2.remove(j)
        except:
            pass
        
elapsed_time2 = ( time.time() - start_time )*1000


## code 3
start_time = time.time()
prime3 = []
check2 = []
k = int(n**0.5)
for i in range(3,n+1,2):
    if i not in check2:
        prime3.append(i)
        if i <= k:
            for j in range(i, n, i+i):
                if j not in check2:
                    check2.append(j)
if n > 1:
    prime3.insert(0,2)
elapsed_time3 = ( time.time() - start_time )*1000

## code 4
start_time = time.time()

prime4 = [i for i in range(11, n+1, 2) if i%3!=0 and i%5!=0 and i%7!=0]
if n > 6:
    prime4.insert(0,7)
if n > 4:
    prime4.insert(0,5)
if n > 2:
    prime4.insert(0,3)
if n > 1:
    prime4.insert(0,2)

for i in range(11,int(n**0.5)+1,2):
    j = i
    while j < n - i:
        j += i+i
        if j in prime4:
            prime4.remove(j)

elapsed_time4 = ( time.time() - start_time )*1000

## code 5
start_time = time.time()

prime5 = [i for i in range(11, n+1, 2) if i%3!=0 and i%5!=0 and i%7!=0]
if n > 6:
    prime5.insert(0,7)
if n > 4:
    prime5.insert(0,5)
if n > 2:
    prime5.insert(0,3)
if n > 1:
    prime5.insert(0,2)

for i in range(11,int(n**0.5)+1,2):
    j = i*i
    while j < n:
        if j in prime5:
            prime5.remove(j)
        j += i+i

elapsed_time5 = ( time.time() - start_time )*1000

print('len1',len(prime),len(check))
print('elapsed time = {} ms'.format(elapsed_time1))

print('len2',len(prime2))
print('elapsed time = {} ms'.format(elapsed_time2))

print('len3',len(prime3),len(check2))
print('elapsed time = {} ms'.format(elapsed_time3))

print('len4',len(prime4))
print('elapsed time = {} ms'.format(elapsed_time4))

print('len5',len(prime5))
print('elapsed time = {} ms'.format(elapsed_time5))

n = 2000

len1 303 1441
elapsed time = 22.9947566986084 ms
len2 303
elapsed time = 17.994403839111328 ms
len3 303 710
elapsed time = 40.98987579345703 ms
len4 303
elapsed time = 7.997751235961914 ms
len5 303
elapsed time = 4.9991607666015625 ms

n = 200

len1 46 129
elapsed time = 1.0006427764892578 ms
len2 46
elapsed time = 0.0 ms
len3 46 59
elapsed time = 0.0 ms
len4 46
elapsed time = 0.0 ms
len5 46
elapsed time = 0.0 ms

>>> prime5
[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]

应该没犯规吧？
筛选生成、筛选结果

Chysial

代码：

# 生成1`200的数，直接生成，采用列表的形式
number = []
prime = []
for i in range(1,201):
    number.append(i)

# 排序
number.sort()

# 筛选

for each in range(199):
    if number[each] == 1:
        number.pop(each)

while number:
    prime.append(number[0])
    for each in number:
        if each % number[0] ==0:
            number.remove(each)
# 输出结果
print(prime)

结果：
[2, 3, 4, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]