'''
Crible d Eratosthènes 23 juillet 2023
'''
def sieve_of_eratosthenes(N):
# Créer une liste de booléens pour marquer les nombres premiers (True) et non premiers (False)
primes = [True] * (N + 1)
primes[0], primes[1] = False, False # 0 et 1 ne sont pas premiers
p = 2
while p * p <= N:
if primes[p]:
# Marquer comme non premier tous les multiples de p à partir de p^2
for i in range(p * p, N + 1, p):
primes[i] = False
p += 1
# Retourner la liste des nombres premiers jusqu'à N
return [num for num, is_prime in enumerate(primes) if is_prime]
def is_prime(num):
# Utiliser le crible d'Ératosthène pour vérifier si le nombre est premier
if num < 2:
return False
primes_list = sieve_of_eratosthenes(num)
return num in primes_list
# Test du crible d'Ératosthène pour trouver tous les nombres premiers jusqu'à N=30
# =========================
N = 1000 # variable ====
# =========================
primes_list = sieve_of_eratosthenes(N)
print("Nombres premiers jusqu'à", N, ":", primes_list)
# Tester la fonction is_prime
num_to_check = 17
if is_prime(num_to_check):
print(num_to_check, "est un nombre premier.")
else:
print(num_to_check, "n'est pas un nombre premier.")
