title: 质数相关问题的python实现 date: 2020-04-12 18:26:26 categories: 算法 tags: [python, 质数]
筛质数（三种筛法）
给定一个正整数n，请你求出1~n中质数的个数。
输入格式
共一行，包含整数n。
输出格式
共一行，包含一个整数，表示1~n中质数的个数。
数据范围
1≤n≤1061≤n≤106
输入样例：
8
输出样例：
4
代码
IAS
=lambda:map(str,input().split
())
IA
=lambda:map(int,input().split
())
n
=int(input())
prime
=[]
st
=[False for i
in range(0,n
+1)]
st
[0]=True
st
[1]=True
def get_prime(N
):
for i
in range(2,N
+1):
if st
[i
]==False:
prime
.append
(i
)
for j
in range(i
+i
,N
+1,i
):
st
[j
]=True
def get_prime(N
):
for i
in range(2,N
+1):
if st
[i
]==False:
prime
.append
(i
)
for j
in range(i
+i
,N
+1,i
):
st
[j
]=True
def get_prime(N
):
for i
in range(2,N
+1):
if st
[i
]==False:
prime
.append
(i
)
for it
in prime
:
if it
*i
>N
:break
st
[it
*i
]=True
if i
%it
==0:
break
get_prime
(n
)
print(len(prime
))
友好搭档 21’
描述
JM在学习了素数之后，决定挑33个素数构成和为nn,并将这样一组的三个数称之为友好搭档
现在，JM同学想知道，它能够找出多少组不同的友好搭档。
例如：(2,2,5)(2,2,5)就是一组和为99的友好搭档
**注意：**同组元素没有先后次序关系，(2,2,5)和(2,5,2)(2,2,5)和(2,5,2)是同一组友好搭档
输入
输入一行，一个正整数nn。
输出
输出和为nn不同友好搭档的数量
样例
输入复制
9
输出复制
2
提示
样例解释
(2,2,5),(3,3,3
数据规模
对于50%50%的数据，1 \le n \le 1001≤n≤100
对于80%80%的数据，1 \le n \le 20001≤n≤2000
对于100%100%的数据，1 \le n \le 800001≤n≤80000
代码
n
=int(input())
N
=n
prime
=[]
st
=[False for i
in range(0,N
+1)]
st
[1]=True
st
[0]=True
def get_prime(N
):
for i
in range(2,N
+1):
if st
[i
]==False:
prime
.append
(i
)
for it
in prime
:
if it
*i
>N
:break
st
[it
*i
]=True
if i
%it
==0:break
get_prime
(N
)
ans
=0
cnt
=len(prime
)
for i
in range(0,cnt
):
for j
in range(i
,cnt
):
k
=n
-prime
[i
]-prime
[j
]
if k
<prime
[j
]:
break
if st
[k
]==False:
ans
+=1
print(ans
)
