Анализ различных методов поиска простого числа в Python

Опубликовано: 19 Января, 2022

Если вы участвуете в соревновательном программировании, вы, возможно, знакомы с тем фактом, что вопросы, связанные с простыми числами, являются одним из вариантов, который может выбрать тот, кто ставит задачи. Здесь мы обсудим, как оптимизировать вашу функцию, которая проверяет простое число в заданном диапазоне, а также рассчитывает время их выполнения.
По определению, простое число - это целое положительное число, которое делится только на себя и 1. Например: 2,3,5,7. Но если число можно разложить на меньшие числа, оно называется составным числом. Например: 4 = 2 * 2, 6 = 2 * 3
И целое число 1 не является ни простым, ни составным числом. Проверить, что число является простым, легко, но для эффективной проверки требуются некоторые усилия.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Method 1 
Let us now go with the very first function to check whether a number, say n, is prime or not. In this method, we will test all divisors from 2 to n-1. We will skip 1 and n. If n is divisible by any of the divisor, the function will return False, else True. 
Following are the steps used in this method: 

  1. If the integer is less than equal to 1, it returns False.
  2. If the given number is divisible by any of the numbers from 2 to n, the function will return False
  3. Else it will return True

Python3

# Python Program to find prime numbers in a range
import time
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2,n):
        if n % i == 0:
            return False
    return True
 
# Driver function
t0 = time.time()
c = 0 #for counting
 
for n in range(1,100000):
    x = is_prime(n)
    c += x
print("Total prime numbers in range :", c)
 
t1 = time.time()
print("Time required :", t1 - t0)

Выход:

 Всего простых чисел в диапазоне: 9592
Требуемое время: 60.702312707901

В приведенном выше коде мы проверяем все числа от 1 до 100000, являются ли эти числа простыми или нет. Как показано, у него огромная среда выполнения. Бег занимает около 1 минуты. Это простой подход, но для его выполнения требуется много времени. Таким образом, это не является предпочтительным в соревновательном программировании.

Способ 2
В этом методе мы используем простой трюк, уменьшая количество проверяемых делителей. Мы обнаружили, что есть тонкая линия, которая действует как зеркало, поскольку показывает факторизацию под линией и факторизацию над линией в обратном порядке. Линия, разделяющая множители на две половины, является линией квадратного корня из числа. Если число является точным квадратом, мы можем сдвинуть строку на 1 и получить целочисленное значение линии, которая делится.

36=1*36          
  =2*18
  =3*12
  =4*9
------------
  =6*6
------------
  =9*4
  =12*3
  =18*2
  =36*1

In this function, we calculate an integer, say max_div, which is the square root of the number and get its floor value using the math library of Python. In the last example, we iterate from 2 to n-1. But in this, we reduce the divisors by half as shown. You need to import the math module to get the floor and sqrt function. 
Following are the steps used in this method: 

  1. If the integer is less than equal to 1, it returns False.
  2. Now, we reduce the numbers which needs to be checked to the square root of the given number.
  3. If the given number is divisible by any of the numbers from 2 to the square root of the number, the function will return False
  4. Else it will return True

Python3

# Python Program to find prime numbers in a range
import math
import time
def is_prime(n):
    if n <= 1:
        return False
 
    max_div = math.floor(math.sqrt(n))
    for i in range(2, 1 + max_div):
        if n % i == 0:
            return False
    return True
 
# Driver function
t0 = time.time()
c = 0 #for counting
 
for n in range(1,100000):
    x = is_prime(n)
    c += x
print("Total prime numbers in range :", c)
 
t1 = time.time()
print("Time required :", t1 - t0)

Выход:

 Всего простых чисел в диапазоне: 9592
Требуемое время: 0.4116342067718506

In the above code, we check all the numbers from 1 to 100000 whether those numbers are prime or not. It takes comparatively lesser time than the previous method. This is a bit tricky approach but makes a huge difference in the runtime of the code. So, it is more preferred in competitive programming. 
Method 3 
Now, we will optimize our code to next level which takes lesser time than the previous method. You might have noticed that in the last example, we iterated through every even number up to the limit which was a waste. The thing to notice is that all the even numbers except two can not be prime number. In this method, we kick out all the even numbers to optimize our code and will check only the odd divisors. 
Following are the steps used in this method: 

  1. If the integer is less than equal to 1, it returns False.
  2. If the number is equal to 2, it will return True.
  3. If the number is greater than 2 and divisible by 2, then it will return False.
  4. Now, we have checked all the even numbers. Now, look for the odd numbers.
  5. If the given number is divisible by any of the numbers from 3 to the square root of the number skipping all the even numbers, the function will return False
  6. Else it will return True

Python3

# Python Program to find prime numbers in a range
import math
import time
def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n > 2 and n % 2 == 0:
        return False
 
    max_div = math.floor(math.sqrt(n))
    for i in range(3, 1 + max_div, 2):
        if n % i == 0:
            return False
    return True
 
# Driver function
t0 = time.time()
c = 0 #for counting
 
for n in range(1,100000):
    x = is_prime(n)
    c += x
print("Total prime numbers in range :", c)
 
t1 = time.time()
print("Time required :", t1 - t0)

Выход:

 Всего простых чисел в диапазоне: 9592
Требуемое время: 0,23305177688598633

In the above code, we check all the numbers from 1 to 100000 whether those numbers are prime or not. It takes comparatively lesser time than all the previous methods for running the program. It is most efficient and quickest way to check for the prime number. Therefore, it is most preferred in competitive programming. Next time while attempting any question in competitive programming, use this method for best results.
Sieve Method 
This method prints all the primes smaller than or equal to a given number, n. For example, if n is 10, the output should be “2, 3, 5, 7”. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19”. 
This method is considered to be the most efficient method to generate all the primes smaller than the given number, n. It is considered as the fastest method of all to generate a list of prime numbers. This method is not suited to check for a particular number. This method is preferred for generating the list of all the prime numbers.

Python3

# Python Program to find prime numbers in a range
import time
def SieveOfEratosthenes(n):
      
    # Create a boolean array "prime[0..n]" and
    # initialize all entries it as true. A value
    # in prime[i] will finally be false if i is
    # Not a prime, else true.
    prime = [True for i in range(n+1)]
     
    p = 2
    while(p * p <= n):
          
        # If prime[p] is not changed, then it is
       # a prime
        if (prime[p] == True):
              
            # Update all multiples of p
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    c = 0
 
    # Print all prime numbers
    for p in range(2, n):
        if prime[p]:
            c += 1
    return c
 
# Driver function
t0 = time.time()
c = SieveOfEratosthenes(100000)
print("Total prime numbers in range:", c)
 
t1 = time.time()
print("Time required:", t1 - t0)

Выход:

 Всего простых чисел в диапазоне: 9592
Требуемое время: 0,0312497615814209

Примечание. Время, необходимое для всех процедур, может варьироваться в зависимости от компилятора, но порядок времени, необходимый для различных методов, останется прежним.

Ссылка :

https: //www.geeksforgeeks.org/sieve-of-eratosthenes/
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Эта статья предоставлена Ришабом Бансалом. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Внимание компьютерщик! Укрепите свои основы с помощью базового курса программирования Python и изучите основы.

Для начала подготовьтесь к собеседованию. Расширьте свои концепции структур данных с помощью курса Python DS. А чтобы начать свое путешествие по машинному обучению, присоединяйтесь к курсу Машинное обучение - базовый уровень.

Python

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Как научиться программировать на Python
6 Июля, 2023
Линейный классификатор в Tensorflow
21 Февраля, 2023
Обнаружение рака кожи с помощью TensorFlow
21 Февраля, 2023
Прогнозирование цены Dogecoin с помощью машинного обучения
21 Февраля, 2023
Красивая печать XML в Python
21 Февраля, 2023
Прогнозирование права на получение ссуды с использованием моделей машинного обучения в Python
21 Февраля, 2023
Квантование цвета с использованием K-Means в Scikit Learn
21 Февраля, 2023
Классификация изображений с использованием набора данных CIFAR-10 и CIFAR-100 в TensorFlow
21 Февраля, 2023