Tous les défis
Moyen 2 résolus 66.7 % de réussite

List Primes With a Sieve

Find primes up to a limit by marking composite multiples.

Ce que vous allez apprendre

  • Mark composite numbers in a boolean array
  • Start crossing out at p × p
  • Collect the remaining primes

Problème

Afficher la traduction

Return all prime numbers from 2 through limit. A prime is an integer greater than 1 divisible only by 1 and itself. Use the sieve idea: keep the next unmarked number and mark its larger multiples as composite. List results in ascending order.

Implement sieve_primes(limit).

Input

limit: The largest number that may be included.

Output

Return the primes in ascending order, or an empty list if none exist.

Contraintes

0 ≤ limit ≤ 100,000. The upper bound is inclusive. Output tests verify results, not the exact algorithm used.

Exemples

Exemple 1
Entrée :
limit = 12

Sortie attendue :
expected = [2, 3, 5, 7, 11]
Entrée :
long long limit = 12;

Sortie attendue :
std::vector<long long> expected = {2, 3, 5, 7, 11};
Entrée :
long limit = 12;

Sortie attendue :
long[] expected = new long[] {2, 3, 5, 7, 11};

Explication

Mark multiples of 2 and 3 as composite. The remaining values up to 12 are 2, 3, 5, 7, and 11.

Exemple 2
Entrée :
limit = 1

Sortie attendue :
expected = []
Entrée :
long long limit = 1;

Sortie attendue :
std::vector<long long> expected = {};
Entrée :
long limit = 1;

Sortie attendue :
long[] expected = new long[] {};

Explication

Prime numbers begin at 2, beyond this limit.

Comment l'aborder

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

Indice 1

Mark composites starting from each unmarked prime candidate and continue through the limit.

Indice 2

Only numbers that stay unmarked at the end are prime.

Indice 3

Stop marking multiples once the candidate’s square exceeds the limit.

Complexité attendue

O(n log log n) time, O(n) 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,002 ms - 5/5 Voir le code
2 KKKaneki Ken Python 1,006 ms - 3/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 2 solutions complètes 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.