すべてのチャレンジ
中級 1件解決済み 正答率100.0%

Sum of Primes Below a Limit

Add all primes strictly below a limit.

このチャレンジで学べること

  • Find all primes below a limit with a sieve
  • Mark multiples instead of testing each number
  • Sum values efficiently

問題

翻訳を表示

A prime is an integer greater than 1 divisible only by 1 and itself. Add every prime strictly smaller than limit. The limit itself is excluded even when it is prime.

Implement prime_sum(limit).

Input

limit: The exclusive upper bound.

Output

Return the sum of the eligible primes, or 0 when none exist.

制約

0 ≤ limit ≤ 2,000,000. Return the sum using a signed 64-bit integer.

例

例 1
入力:
limit = 12

期待される出力:
expected = 28
入力:
long long limit = 12;

期待される出力:
long long expected = 28;
入力:
long limit = 12;

期待される出力:
long expected = 28;

解説

The primes below 12 are 2, 3, 5, 7, and 11; their sum is 28.

例 2
入力:
limit = 2

期待される出力:
expected = 0
入力:
long long limit = 2;

期待される出力:
long long expected = 0;
入力:
long limit = 2;

期待される出力:
long expected = 0;

解説

There are no primes strictly below 2.

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

The main cost is finding primes efficiently; naive divisibility checks for every number will be too slow.

ヒント 2

Use a sieve-like approach to mark composites, then add the numbers that remain unmarked and below the limit.

ヒント 3

Remember that the limit itself is excluded, even when it is prime, and small limits may contribute nothing.

目安の計算量

O(limit log log limit) time, O(limit) extra space

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

# コーダー 言語 時間 メモリ AI 評価 解答
1 ННикита Python 1,057 ms - 4/5 コードを見る

他の人の解答から学ぶ

コミュニティの解答

ネタバレ注意:下に1件の全解答あり まずは自分で挑戦してみましょう。他の開発者のコードやAIレビューも見ることができます。 サインインして課題を解くと議論に参加できます。