Самый быстрый метод Python для вычисления всех простых чисел

Обзор вычислительных простых чисел из данной серии чисел не может быть большим вопросом. Тем не менее, вычисляющие простые простые простые простые способы сохранения временной сложности и другие факторы, могут быть сложным вопросом. В конце концов, одним из основных критериев эффективного кода является его эффективность. Следовательно В этой статье … Самый быстрый метод Python для вычисления всех простых чисел

• Автор записи Автор: Shubham Sayon
• Дата записи 24.09.2021

import time
start_time = time.time()
n = int(input("Enter the last range of the series: "))
for i in range(1,n+1):
  if i>1:
    for j in range(2,i):
        if(i % j==0):
            break
    else:
        print(i)
end_time = time.time()
print("Elapsed Time: " + str(end_time-start_time))

Enter the last range of the series: 10
2
3
5
7
Elapsed Time: 3.9661035537719727

from sympy import sieve
import numpy
import itertools

izip = itertools.zip_longest
chain = itertools.chain.from_iterable
compress = itertools.compress
import time


def method1(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def method2(n):
    """ Returns  a list of primes < n """
    sieve = [True] * (n // 2)
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i // 2]:
            sieve[i * i // 2::i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [2 * i + 1 for i in range(1, n // 2) if sieve[i]]


def method3(n):
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = numpy.ones(n // 3 + (n % 6 == 2), dtype=numpy.bool)
    for i in range(1, int(n ** 0.5) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3::2 * k] = False
            sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = False
    return numpy.r_[2, 3, ((3 * numpy.nonzero(sieve)[0][1:] + 1) | 1)]


def method4(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
    sieve = [True] * (n // 3)
    for i in range(1, int(n ** 0.5) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
            sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * (
                    (n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
    return [2, 3] + [3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]]


def method5(n):
    primes = list(sieve.primerange(1, n))
    return primes


def method6(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    zero = bytearray([False])
    size = n // 3 + (n % 6 == 2)
    sieve = bytearray([True]) * size
    sieve[0] = False
    for i in range(int(n ** 0.5) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            start = (k * k + 4 * k - 2 * k * (i & 1)) // 3
            sieve[(k * k) // 3::2 * k] = zero * ((size - (k * k) // 3 - 1) // (2 * k) + 1)
            sieve[start::2 * k] = zero * ((size - start - 1) // (2 * k) + 1)
    ans = [2, 3]
    poss = chain(izip(*[range(i, n, 6) for i in (1, 5)]))
    ans.extend(compress(poss, sieve))
    return ans


m1_start = time.time()
method1(10 ** 6)
m1_end = time.time()
m1_et = m1_end - m1_start
print("Method 1 Elapsed time: " + str(m1_end - m1_start))

m2_start = time.time()
method2(10 ** 7)
m2_end = time.time()
m2_et = m2_end - m2_start
print("Method 2 Elapsed time: " + str(m2_end - m2_start))

m3_start = time.time()
method3(10 ** 7)
m3_end = time.time()
m3_et = m3_end - m3_start
print("Method 3 Elapsed time: " + str(m3_end - m3_start))

m4_start = time.time()
method4(10 ** 7)
m4_end = time.time()
m4_et = m4_end - m4_start
print("Method 4 Elapsed time: " + str(m4_end - m4_start))

m5_start = time.time()
method5(10 ** 7)
m5_end = time.time()
m5_et = m5_end - m5_start
print("Method 5 Elapsed time: " + str(m5_end - m5_start))

m6_start = time.time()
method6(10 ** 7)
m6_end = time.time()
m6_et = m6_end - m6_start
print("Method 6 Elapsed time: " + str(m6_end - m6_start))

Method 1 Elapsed time: 0.06881570816040039
Method 2 Elapsed time: 0.9155552387237549
Method 3 Elapsed time: 0.045876264572143555
Method 4 Elapsed time: 0.6512553691864014
Method 5 Elapsed time: 7.0082621574401855
Method 6 Elapsed time: 0.33211350440979004

from math import sqrt
import time


def method1(max_n):
    numbers = range(3, max_n + 1, 2)
    half = (max_n) // 2
    initial = 4

    for step in range(3, max_n + 1, 2):
        for i in range(initial, half, step):
            numbers[i - 1] = 0
        initial += 2 * (step + 1)

        if initial > half:
            return [2] + filter(None, numbers)


def method2(n):
    """sieveOfEratosthenes(n): return the list of the primes < n."""
    if n <= 2:
        return []
    sieve = range(3, n, 2)
    top = len(sieve)
    for si in sieve:
        if si:
            bottom = (si * si - 3) // 2
            if bottom >= top:
                break
            sieve[bottom::si] = [0] * -((bottom - top) // si)
    return [2] + [el for el in sieve if el]


def method3(n):
    s = range(3, n, 2)
    for m in xrange(3, int(n ** 0.5) + 1, 2):
        if s[(m - 3) / 2]:
            for t in xrange((m * m - 3) / 2, (n >> 1) - 1, m):
                s[t] = 0
    return [2] + [t for t in s if t > 0]


def method4(size):
    prime = [True] * size
    rng = xrange
    limit = int(sqrt(size))
    for i in rng(3, limit + 1, +2):
        if prime[i]:
            prime[i * i::+i] = [False] * len(prime[i * i::+i])

    return [2] + [i for i in rng(3, size, +2) if prime[i]]


m1_start = time.time()
method1(10 ** 6)
m1_end = time.time()
print("Method 1 Elapsed time: " + str(m1_end - m1_start))

m2_start = time.time()
method2(10 ** 6)
m2_end = time.time()
print("Method 2 Elapsed time: " + str(m2_end - m2_start))

m3_start = time.time()
method3(10 ** 6)
m3_end = time.time()
print("Method 3 Elapsed time: " + str(m3_end - m3_start))

m4_start = time.time()
method4(10 ** 6)
m4_end = time.time()
print("Method 4 Elapsed time: " + str(m4_end - m4_start))

Method 1 Elapsed time: 0.891271114349
Method 2 Elapsed time: 0.178880214691
Method 3 Elapsed time: 0.526117086411
Method 4 Elapsed time: 0.29536986351

import plot
import matplotlib.pyplot as plt
import numpy as np

method = ['Method 1', 'Method 2', 'Method 3', 'Method 4', 'Method 5', 'Method 6']
et = [plot.m1_et, plot.m2_et, plot.m3_et, plot.m4_et, plot.m5_et, plot.m6_et]
c = ["red", "green", "orange", "blue", "black", "purple"]
ypos = np.arange(len(method))
plt.xticks(ypos, method)
plt.bar(ypos, et, 0.4, color=c)
plt.title("Time To Compute Primes")
plt.xlabel("Methods")
plt.ylabel("Elapsed Time (seconds)")
plt.show()

import plot
import matplotlib.pyplot as plt
import numpy as np
method = ['Method 1', 'Method 2', 'Method 3', 'Method 4', 'Method 5', 'Method 6']
et = [plot.m1_et, plot.m2_et, plot.m3_et, plot.m4_et, plot.m5_et, plot.m6_et]
ypos = np.arange(len(method))
plt.xticks(ypos, method)
plt.plot(ypos, et, color='green', linestyle='dashed', linewidth = 3,
         marker='o', markerfacecolor='blue', markersize=12)
plt.title("Time To Compute Primes")
plt.xlabel("Methods")
plt.ylabel("Elapsed Time (seconds)")
plt.show()