Tous les défis
Moyen 1 résolu 100.0 % de réussite

Sum of Primes Below a Limit

Add all primes strictly below a limit.

Ce que vous allez apprendre

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

Problème

Afficher la traduction

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.

Contraintes

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

Exemples

Exemple 1
Entrée :
limit = 12

Sortie attendue :
expected = 28
Entrée :
long long limit = 12;

Sortie attendue :
long long expected = 28;
Entrée :
long limit = 12;

Sortie attendue :
long expected = 28;

Explication

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

Exemple 2
Entrée :
limit = 2

Sortie attendue :
expected = 0
Entrée :
long long limit = 2;

Sortie attendue :
long long expected = 0;
Entrée :
long limit = 2;

Sortie attendue :
long expected = 0;

Explication

There are no primes strictly below 2.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

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

Indice 2

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

Indice 3

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

Complexité attendue

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

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 1,057 ms - 4/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.