Alle Herausforderungen
Mittel 1 gelöst 100.0% Erfolgsquote

Summe der Primzahlen unterhalb eines Grenzwerts

Addiere alle Primzahlen strikt unterhalb eines Grenzwerts.

Das lernst du

  • Alle Primzahlen unter einer Grenze mit einem Sieb finden
  • Vielfache markieren statt jede Zahl zu testen
  • Werte effizient summieren

Problem

Eine Primzahl ist eine ganze Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist. Addiere alle Primzahlen, die strikt kleiner als limit sind. Der Grenzwert selbst wird auch dann ausgeschlossen, wenn er eine Primzahl ist.

Implementiere prime_sum(limit).

Eingabe

limit: Die exklusive obere Grenze.

Ausgabe

Gib die Summe der zutreffenden Primzahlen zurück, oder 0, wenn keine existieren.

Einschränkungen

0 ≤ limit ≤ 2.000.000. Gib die Summe als vorzeichenbehaftete 64-Bit-Ganzzahl zurück.

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

Die Primzahlen unterhalb von 12 sind 2, 3, 5, 7 und 11; ihre Summe ist 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

Es gibt keine Primzahlen strikt unterhalb von 2.

So gehst du vor

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

Hinweis 1

Der Hauptaufwand liegt darin, Primzahlen effizient zu finden; naive Teilbarkeitsprüfungen für jede Zahl sind zu langsam.

Hinweis 2

Nutze einen siebähnlichen Ansatz, um zusammengesetzte Zahlen zu markieren, und addiere dann die Zahlen, die unmarkiert unter dem Limit bleiben.

Hinweis 3

Denk daran, dass das Limit selbst ausgeschlossen ist, auch wenn es prim ist, und kleine Limits eventuell nichts beitragen.

Erwartete Komplexität

Zeit O(limit log log limit), zusätzlicher Speicher O(limit)

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.