結果

問題 No.1657 Sum is Prime (Easy Version)
コンテスト
ユーザー ID 21712
提出日時 2026-05-11 01:00:48
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
TLE  
実行時間 -
コード長 1,117 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,812 ms
コンパイル使用メモリ 282,888 KB
実行使用メモリ 18,668 KB
最終ジャッジ日時 2026-05-11 01:01:55
合計ジャッジ時間 18,363 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "math/big"

func main() {
	var l,r int
	Scan(&l,&r)
	ans := 0
	for i := 2; i < 2*r+1; i++ {
		if !NewInt(int64(i)).ProbablyPrime(0) {
			continue
		}
		if l <= i && i <= r {
			ans++
		}
		if i > 2 && l <= i/2 && i/2+1 <= r {
			ans++
		}
	}
	Println(ans)
}

/*
考察

A + (A+1) + ... + B

N = B - A + 1
A = X + 1
B = X + N
と置くと

(X+1) + (X+2) + ... + (X+N)

となり、整理すると

N*X + (1+2+ ... +N)
= N*X + N*(1+N)/2
= N * (2*X + (1+N)) / 2

これは N >= 3 では A+...+B は常に合成数であることを意味する
N = 1 は A = B であり、つまり A 自体が素数かどうか
N = 2 は A+1 = B であり、つまり 2*A+1 が素数かどうか

したがって
2*R 以下の素数pで
・素数p自体がL以上R以下 L <= p <= R
・素数pの切り捨て半分とその+1がL以上R以下 L <= floor(p/2) < floor(p/2)+1 <= R
を数えればよい
2*R は最大でも 2*10^6 なのでエラトステネスの篩での素数列挙で間に合う

Hardのほう、Rの最大が10^10ということで、どうやるのか全くわからんね


*/
0