範囲[1、N]の少なくとも1つの素数で割り切れる範囲[L、R]の数を数える効率的なアルゴリズム

Question

N、LおよびRが与えられた場合、範囲[ L、R]は範囲[1、N]の少なくとも1つの素数で割り切れる。

制約：

1<=N<=50 
1<=L,R<=10^18 

例：

N=5 
L=1 
R=10 

回答= 8

説明：範囲[1,5]である{2,3における

素数5}。 {2,3,5}の素数の少なくとも1つで割り切れる範囲[1,10]の数字は{2,3,4,5,6,8,9,10}です。

制約が高すぎるため、Pythonのコードで「時間制限超過」エラーが発生しています。

マイコード：

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が挑戦、Hackerearthを雇うからのものであり、課題は今の上にあると編集が提供されていません！

Answer 1

素数配列には50未満の素数が含まれます。素数配列のサイズは15です。以下のコード）。だから、必要な素数ごとに同じことをする必要があります。しかし、正しい結果を得るためには、包含 - 除外を実行する必要があります。複雑さはO（2^P）です。 PはNよりも大きくない素数の数です。2^Pは最大で2^15になります。

N, L, R, = map(int,raw_input().split()) 

    def calculateInterval(begin,end,number): 
     return (end/number) - ((begin-1)/number) 

    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] 

    end = 0 
    while end < 15: 
     if primes[end] > N: 
      break 
     end += 1 

    res = 0 
    i = 1 
    while i < (1<<end): 

     cnt = 0 
     num = 1 

     for j in xrange(end): 
      if (1<<j) & i: 
       cnt += 1 
       num *= primes[j] 

     if cnt%2 == 1: 
      res += calculateInterval(L,R,num) 
     else: 
      res -= calculateInterval(L,R,num) 

     i += 1 

    print res