Alle Herausforderungen
Mittel 1 gelöst 100.0% Erfolgsquote

Sum of Primes Below a Limit

Add all primes strictly below a limit.

Das lernst du

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

Problem

Übersetzung anzeigen

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.

Einschränkungen

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

Beispiele

Beispiel 1
Eingabe:
limit = 12

Erwartete Ausgabe:
expected = 28
Eingabe:
long long limit = 12;

Erwartete Ausgabe:
long long expected = 28;
Eingabe:
long limit = 12;

Erwartete Ausgabe:
long expected = 28;

Erläuterung

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

Beispiel 2
Eingabe:
limit = 2

Erwartete Ausgabe:
expected = 0
Eingabe:
long long limit = 2;

Erwartete Ausgabe:
long long expected = 0;
Eingabe:
long limit = 2;

Erwartete Ausgabe:
long expected = 0;

Erläuterung

There are no primes strictly below 2.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

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

Hinweis 2

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

Hinweis 3

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

Erwartete Komplexität

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

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 1,057 ms - 4/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.