Эффективный алгоритм для подсчета чисел в диапазоне [L, R], которые делятся по крайней мере на одно простое число в диапазоне [1, N]

Question

Учитывая N, L и R, мне нужно найти количество чисел в диапазоне [ L, R], которые делятся по крайней мере на одно простое число в диапазоне [1, N].

Ограничения:

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

Пример:

N=5 
L=1 
R=10 

ответа = 8

Пояснение:

Простые числа в диапазоне [1,5] являются {2,3, 5}. Числа в диапазоне [1,10], которые делятся по крайней мере на один из простых чисел в {2,3,5}, являются {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. Вы можете рассчитать, сколько чисел в интервале [L, R] делится на число с сложностью O (1) (вычисляет функциюInterval в код ниже). Поэтому вы должны сделать то же самое для каждого необходимого простого числа. Но вы должны выполнить исключение включения для правильного результата. Сложность - 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