Encuentra todos los números primos menores o iguales a N utilizando la criba de Eratóstenes algoritmo en Python

En este tutorial, vamos a aprender cómo encontrar todos los números primos menores o iguales a N mediante el uso de la criba de Eratóstenes algoritmo en un lenguaje de programación Python?

Como todos sabemos que el número primo es un número entero mayor que 1 que sólo es divisible por 1 o sí. class ejemplo 2,3,5,7,11, .. etc. El valor de N está dada por el usuario. Antes de ir a resolver este problema, vamos a aprender un poco sobre el criba de Eratóstenes y es un algoritmo.

¿Cuál es el criba de Eratóstenes?

Es un método simple y antigua For encontrar todos los números primos menores o iguales a N .

Algoritmo para encontrar números primos por criba de Eratóstenes

  1. Inicialmente, vamos a crear una matriz for de tamaño igual al N y marcar cada posición en la matriz verdadera.
  2. inicializamos una variable p como 2. Si la variable es primo, entonces marcar cada múltiplo de número falso de la matriz y actualizar la variable p por incremento.
  3. Repita paso 2 hasta que el cuadrado de la variable p es menor que o igual a N .
  4. boolean, los elementos de la matriz con True contiene todos los números primos.

Aplicación del algoritmo anterior utilizando el programa pitón

# input the value of N
N=int(input("Input the value of N: "))
Primes=[True for k in range(N+1)]
p=2
Primes[1]=False
Primes[0]=False
while(p*p<=N):
if Primes[p]==True:
for j in range(p*p,N+1,p):
Primes[j]=False
p+=1
for i in range(2,N):
if Primes[i]:
print(i,end=' ')

salida

Input the value of N: 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *