結果

問題 No.1661 Sum is Prime (Hard Version)
ユーザー tomo0608tomo0608
提出日時 2021-08-27 23:26:20
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,204 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 1,033,276 KB
最終ジャッジ日時 2024-11-21 05:25:33
合計ジャッジ時間 48,271 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
81,024 KB
testcase_01 AC 85 ms
509,568 KB
testcase_02 TLE -
testcase_03 WA -
testcase_04 AC 69 ms
81,108 KB
testcase_05 AC 83 ms
502,228 KB
testcase_06 AC 84 ms
82,212 KB
testcase_07 AC 68 ms
83,644 KB
testcase_08 AC 69 ms
80,512 KB
testcase_09 AC 83 ms
463,552 KB
testcase_10 AC 68 ms
80,640 KB
testcase_11 AC 82 ms
503,604 KB
testcase_12 MLE -
testcase_13 MLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 AC 1,813 ms
291,100 KB
testcase_19 TLE -
testcase_20 AC 1,650 ms
293,380 KB
testcase_21 TLE -
testcase_22 TLE -
testcase_23 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect

def prime_sieve(n):
    """
    Efficient prime sieve, due to Robert William Hanks.
    Source: http://stackoverflow.com/a/2068548
    """
    sieve = [True] * ((n+1)//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]

"""
Limit controls the number of primes that are sieved
to cache small values of pi(x).  Without caching,
runtime will be exponential.
When computing pi(x), limit should be
at least sqrt(x).  A higher value of limit
that caches more values can sometimes improve performance.
"""

limit = 10**6
primes = prime_sieve(limit)


phi_cache = {}
def phi(x, a):
    """
    Implementation of the partial sieve function, which
    counts the number of integers <= x with no prime factor less
    than or equal to the ath prime.
    """
    # If value is cached, just return it
    if (x, a) in phi_cache: return phi_cache[(x, a)]

    # Base case: phi(x, a) is the number of odd integers <= x
    if a == 1: return (x + 1) // 2

    result = phi(x, a-1) - phi(x // primes[a-1], a-1)
    phi_cache[(x, a)] = result # Memoize
    return result


pi_cache = {}
def pi(x):
    """
    Computes pi(x), the number of primes <= x, using
    the Meissel-Lehmer algorithm.
    """
    # If value is cached, return it
    if x in pi_cache: return pi_cache[x]

    # If x < limit, calculate pi(x) using a bisection
    # algorithm over the sieved primes.
    if x < limit:
        result = bisect(primes, x)
        pi_cache[x] = result
        return result

    a = pi(int(x ** (1./4)))
    b = pi(int(x ** (1./2)))
    c = pi(int(x ** (1./3)))

    # This quantity must be integral,
    # so we can just use integer division.
    result = phi(x,a) + (b+a-2) * (b-a+1) // 2

    for i in range(a+1, b+1):
        w = x / primes[i-1]
        b_i = pi(w ** (1./2))
        result = result - pi(w)
        if i <= c:
            for j in range(i, b_i+1):
                result = result - pi(w / primes[j-1]) + j - 1
    pi_cache[x] = result
    return result

l,r = map(int,input().split())
print(int(pi(r) - pi(l-1) + pi(2*r-1) - pi(2*l)))
0