Python：每日一题 205

冬雪雪冬 · 发表于 2018-9-2 10:54:27

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由冬雪雪冬于 2018-9-8 19:05 编辑

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

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

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

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

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

凌九霄 · 发表于 2018-9-2 11:04:24

本帖最后由凌九霄于 2018-9-4 01:29 编辑

本代码中，最耗时的是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))

复制代码

塔利班 · 发表于 2018-9-2 11:08:42

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

复制代码

拉了盏灯 · 发表于 2018-9-2 11:21:56

本帖最后由拉了盏灯于 2018-9-2 12:16 编辑

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

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 · 发表于 2018-9-2 11:55:18

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 = " ")

复制代码

靳泽宇 · 发表于 2018-9-2 12:20:07

本帖最后由靳泽宇于 2018-9-2 12:22 编辑

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

黑白、 · 发表于 2018-9-2 15:33:53

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

复制代码

子沙 · 发表于 2018-9-2 16:43:33

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)

复制代码

在东边 · 发表于 2018-9-2 17:43:23

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 · 发表于 2018-9-2 17:52:39

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 · 发表于 2018-9-2 20:09:10

>>> 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 · 发表于 2018-9-2 20:18:35

本帖最后由 JessiFly 于 2018-9-2 20:19 编辑

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 · 发表于 2018-9-2 21:41:04

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]]

复制代码

天圆突破 · 发表于 2018-9-2 23:12:41

本帖最后由天圆突破于 2018-9-2 23:19 编辑

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))

复制代码

晓屁屁 · 发表于 2018-9-3 14:16:26

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 · 发表于 2018-9-3 15:53:29

本帖最后由 chongchuigu 于 2018-9-3 15:55 编辑

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))

复制代码

绝境凤凰 · 发表于 2018-9-3 16:10:26

啊啊啊啊啊啊啊啊啊啊a

祥哥威武 · 发表于 2018-9-3 17:20:57

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 · 发表于 2018-9-3 18:10:21

尝试了 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 · 发表于 2018-9-3 19:20:52

代码：

# 生成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]

账号		自动登录	找回密码
密码			立即注册

[技术交流] Python：每日一题 205

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

评分

评分

评分

点评

点评

评分

评分

点评

评分

评分

评分

评分

评分

评分

评分

评分

评分

浏览过的版块