给定N,L和R,我必须找到范围[L,R]中可被范围[1,N]中至少一个素数整除的数。在
限制条件:
1<=N<=50
1<=L,R<=10^18
示例:
^{pr2}$答案=8
说明:
在[1,5]范围内的质数是{2,3,5}。 [1,10]范围内可被{2,3,5}中至少一个素数整除的数是{2,3,4,5,6,8,9,10}。在
我用Python编写的代码由于约束太高而出现“timelimitexceeded”错误!在
我的代码:
import math
def primes_till_n(n):
sieve=[True]*n
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
return [2]+[i for i in xrange(3,n,2) if sieve[i]]
n,l,r=map(int,raw_input().split())
primes=primes_till_n(n+1)
ct=0
for i in xrange(l,r+1):
for j in primes:
if i%j==0:
ct+=1
break
print ct
这个问题来自Globalsoft招聘挑战,HackerThreath,挑战已经结束,社论不提供!在
让素数数组包含小于50的素数。素数数组的大小为15。您可以计算区间[L,R]中有多少个数可以被一个复杂度为O(1)的数字整除(下面代码中的calculateInterval函数)。所以你应该对每个必要的素数都做同样的处理。但为了得到正确的结果,您应该执行包含排除。复杂性是O(2^P)。P是不大于N的素数。2^P最大为2^15
相关问题 更多 >
编程相关推荐