programa de Python para calcular números primos (utilizando diferentes algoritmos) hasta n

Python imprimación números algoritmos : Aquí, vamos a comparar diferentes algoritmos para calcular números primos upto n plazo en pitón .

Hay varios métodos a través del cual podemos calcular números primos hasta n .

1) Método General

En este método, que generalmente se ejecuta dos class bucles en la que el primero se utiliza para aumentar el número y la segunda se utiliza para comprobar si el número es primo o no. Segundo carreras de bucle de 2 a (n / 2 + 1) (for mejor rendimiento).

Nota: Este es el método menos eficiente (uno no debe usar esta opción si se requiere eficiencia.)

2) la raíz cuadrada Método

En este método, dos bucles se ejecutan primero es aumentar el número y la segunda es para comprobar si el número es primo o no. El segundo bucle se extiende desde 2 a raíz cuadrada (número) (un número que es ser cheque), que es la razón por la longitud de ejecución de segundo bucle for es relativamente pequeño, que es por eso que es eficiente que el enfoque ingenuo.

3) Criba de Eratóstenes

Esta es la mejor y más eficiente método para el cálculo de los números primos hasta n.

Algoritmo for criba de Eratóstenes:

  1. Let A ser una matriz de 2 a n .
    Establecer todos los valores a verdadera (estamos considerando todos los números para ser el Primer)
  2. for bucle desde p == 2 (número primo más pequeño)
  3. class bucle desde p2 de n
    marcar todos los múltiplos de p como Falso y aumentar el valor de p al siguiente número primo
  4. fin del segundo bucle class
  5. fin del primer bucle class

al final de tanto los bucles For, todos los valores que están marcados como TRUE son números primos y todos los números compuestos están marcados como FALSO en el paso 3.

complejidad de tiempo: O (n * log (log (n)))

Nota: Rendimiento del Método general y Método SquareRoot se puede aumentar un poco, comprobamos si sólo los números impares porque en lugar de 2 sin número par es primo.

Ejemplo:

from time import time
from math import sqrt
def general_approach(n):
'''
    Generates all the prime numbers from 2 to n - 1.
    n - 1 is the largest potential prime considered.
    '''
start = time()
count = 0
for i in range(2, n):
flag = 0
x = i // 2 + 1
for j in range(2, x):
if i % j == 0:
flag = 1
break
if flag == 0:
count += 1
stop = time()
print("Count =", count, "Elapsed time:", stop - start, "seconds")
def count_primes_by_sqrt_method(n):
'''
    Generates all the prime numbers from 2 to n - 1.
    n - 1 is the largest potential prime considered.
    '''
start = time()
count = 0
for val in range(2, n):
root = round(sqrt(val)) + 1
for trial_factor in range(2, root):
if val % trial_factor == 0:
break
else:
count += 1
stop = time()
print("Count =", count, "Elapsed time:", stop - start, "seconds")
def seive(n):
'''
    Generates all the prime numbers from 2 to n - 1.
    n - 1 is the largest potential prime considered.
    Algorithm originally developed by Eratosthenes.
    '''
start = time()
# Each position in the Boolean list indicates
# if the number of that position is not prime:
# false means "prime," and true means "composite."
# Initially all numbers are prime until proven otherwise
nonprimes = n * [False]
count = 0
nonprimes[0] = nonprimes[1] = True
for i in range(2, n):
if not nonprimes[i]:
count += 1
for j in range(2*i, n, i):
nonprimes[j] = True
stop = time()
print("Count =", count, "Elapsed time:", stop - start, "seconds")
# Time complexity : O(n*log(log(n)))
def main():
print("For N == 200000n")
print('Sieve of Eratosthenes Method')
seive(200000)
print('nSquare Root Method')
count_primes_by_sqrt_method(200000)
print('nGeneral Approach')
general_approach(200000)
main()

salida

For N == 200000
Sieve of Eratosthenes Method
Count = 17984 Elapsed time: 0.050385475158691406 seconds
Square Root Method
Count = 17984 Elapsed time: 0.9392056465148926 seconds
General Approach
Count = 17984 Elapsed time: 101.83296346664429 seconds


Deja un comentario

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