python求素数的个数

Question

如题所述

Answer 1

求素数本质上的算法还是：除了1和它本身之外的数都不能整除的数。

在网上看到了一种用一行就解决的代码：

" ".join("%s" % x for x in range(2,100) if not [y for y in range(2,x) if x%y == 0])
对这段代码分解，最后一段列表生成式[y for y in range(2,x) if x%y == 0]这个就是核心算法y是从2到x-1的数，x只要能对y整除，配上前面的if not，就是，x不能被2到x-1的数整除，再看前面一段，x for x in range(2,100) 其实就是让x从2到100的取值。我们这假设题目就是求100内的素数。其实代码到这就得出结果了，只要在这些代码外面加上[]就是一个列表生成式了：

[x for x in range(2,100) if not [y for y in range(2,x) if x%y == 0]]
那么为什么还加上了" ".join("%s" % 。。。)这段代码呢？其实只是格式化美观罢了，"%s" %是一种字符串格式化的语法， 基本用法是将值插入到%s占位符的字符串中，join() 方法用于将序列中的元素以指定的字符连接生成一个新的字符串。
下面是结果：

'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'
这样解析出来是个字符串还不能分割，所以我重新改了一下：

a = (" ".join("%s" % x for x in range(2,100) if not [y for y in range(2,x) if x%y == 0])).split()
list1 = []
for item in (a):
list1.append(int(item))
print(list1)
split()把字符串解析成列表，然后给列表每一项都转化成数字。
在数学里，我们还有种判断素数的简化方法:即y的取值范围是2到x的平方根+1

import math
(" ".join("%s" % x for x in range(2,100) if not [y for y in range(2, int(math.sqrt(x))+1) if x%y == 0])).split()
下面是一种正常的算法：
import math
num = []
i = 2
for i in range(2,100):
j = 2;
for j in range(2,int(math.sqrt(i)+1)):
if (i%j==0):
break;
else:
num.append(i)
print(num)

Answer 2

#!/usr/bin/env python3

import datetime

def susu(n):

sulist=[2,3]

if n ==2:

return sulist

m = 3

i=2

while len(sulist)<n:

add=1

if m==sulist[-1]:

m +=2

for i in sulist:

if m%i==0 and i<=sulist[-1]//2:

m+=2

add=0

break

if add:

sulist.append(m)

return sulist

N=1000

begintime=datetime.datetime.now()

for x in susu(N):

#print(x,end = ' ')

pass

# print(susu(N))

endtime=datetime.datetime.now()

print('susu时间:',endtime - begintime)

def _odd_iter():

n = 1

while True:

n = n + 1

yield n

def _not_divisible(n):

return lambda x: x % n > 0

def primes():

it = _odd_iter() # 初始序列

while True:

n = next(it) # 返回序列的第一个数

yield n

it = filter(_not_divisible(n), it) # 构造新序列

begintime=datetime.datetime.now()

i=0

for n in primes():

i+=1

# print(n,end=' ')

if i >N-1:

break

endtime=datetime.datetime.now()

print('primes1时间:',endtime - begintime)

def _odd_iter():

n = 5

while True:

yield n

n = n + 2

yield n

n=n+4

def _not_divisible(n):

return lambda x: x % n > 0

def primes():

yield 2

yield 3

it = _odd_iter() # 初始序列

while True:

n = next(it) # 返回序列的第一个数

yield n

it = filter(_not_divisible(n), it) # 构造新序列

begintime=datetime.datetime.now()

i=0

for n in primes():

i+=1

# print(n,end=' ')

if i >N-1:

break

endtime=datetime.datetime.now()

print('primes时间:',endtime - begintime)

input()

我以前比较素数的算法速度的,自己修改一下吧,复制时注意标点和缩进

Answer 3

哥呵呵好吧巴巴爸爸哈哈哈巴巴爸爸巴巴爸爸巴巴爸爸巴巴爸爸巴巴爸爸