AcWing 3614. 梅森素数(Python3:线性筛)
原题链接
简单
作者:
抹茶味盛夏
,
2023-01-10 16:07:39
,
所有人可见
,
阅读 133
def get_primes(x):
global st,primes,wz
for i in range(2,x):
if not st[i]:
primes[wz]=i
wz+=1
j=0
while primes[j]<=x/i:
st[primes[j]*i]=True
if i%primes[j]==0:
break
j+=1
def is_primes(x):
for i in range(2,int(x**(0.5))+1):
if x%i==0:
return False
return True
wz=0
#由数据范围确定N
N=32
st=[False]*(N+1)
primes=[0]*(N+1)
get_primes(N)
n=eval(input())
for i in range (31):
if is_primes(2**primes[i]-1) and 2**primes[i]-1<=n and primes[i]>0:
print("M({})={}".format(primes[i],2**primes[i]-1))