結果

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

ソースコード

diff #
raw source code 

package main

import . "fmt"

func main() {
	var l,r int
	Scan(&l,&r)
	flag := make([]bool, r*2+1)
	ans := 0
	for i := 2; i < len(flag); i++ {
		if flag[i] {
			continue
		}
		if l <= i && i <= r {
			ans++
		}
		if i > 2 && l <= i/2 && i/2+1 <= r {
			ans++
		}
		for j := i+i; j < len(flag); j += i {
			flag[j] = true
		}
	}
	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