問題一覧 > 通常問題

No.732 3PrimeCounting

レベル : / AI推定難易度 : 1225 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 101
作問者 : startcpp / テスター : platypus999
お気に入りにしたユーザー ProblemId : 1490 / 自分の提出
問題文最終更新日: 2026-06-26 06:08:11
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 199 (順位表) の他の問題:

Problem Statement

Among the triples $(a, b, c) (2 \le a < b < c \le N)$ of $3$ distinct prime numbers not exceeding $N$, how many are such that $a + b + c$ is prime?

Input

$N$

$5 \le N \le 100000$

Output

Output the number (an integer) of triples of primes (a,b,c) satisfying the condition.
Print a newline at the end.

Sample

Sample 1
Input
11
Output
2

The primes not exceeding 11 are the 5 primes 2,3,5,7,11, so there are 10 combinations of (a,b,c).
Among them,
3 + 5 + 11 = 19
5 + 7 + 11 = 23
these 2 satisfy the condition.

Sample 2
Input
1000
Output
241580

Sample 3
Input
10000
Output
74588542

Sample 4
Input
100000
Output
28694800655

Note that the answer does not fit in a 32-bit integer type.
Also, the intended solution only barely passes in $Pypy3$, so we recommend writing in a language faster than $Pypy3$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。