BOJ 1644小数の連続和


https://www.acmicpc.net/problem/1644
2秒、128 MBメモリ
input :
  • N (1 ≤ N ≤ 4,000,000)
  • output :
  • 出力
  • 思ったより時間がかかりました…
    これは同じダブルポインタの問題です.
    アラトネスのふるいで400万個の数字を確認できますが...
    n+1個までチェックしましょう.効率的に
    また,入力受信時に1以上の自然数を入力し,例外処理を行わずにインデックスエラーが発生する.
    tempがn=1より大きいときにやりましょう
    import sys
    n = int(sys.stdin.readline())
    nums = []
    
    prime_num = [1] * (n + 1)
    prime_num[0] = 0
    prime_num[1] = 0
    
    for i in range(2, n + 1):
        for j in range(i + i, n + 1, i):
            prime_num[j] = 0
    
    for idx, item in enumerate(prime_num):
        if item:
            nums.append(idx)
    
    start, end, ans = 0, 0, 0
    if n > 1:
        temp = nums[start]
    
    while start < len(nums):
        if temp >= n:
            if temp == n:
                ans += 1
            temp -= nums[start]
            start += 1
        else:
            if end == len(nums):
                break
            end += 1
            if end != len(nums):
                temp += nums[end]
    print(ans)