Интервью на Python: Простые числа

Автор оригинала: Michael.

Напишите программу, чтобы составить список всех простых чисел меньше 20.

Прежде чем начать, важно отметить, что такое простое число.

1. Простое число должно быть положительным целым числом
2. Делится ровно на 2 целых числа (1 и само по себе)
3. 1 не является простым числом

Хотя существует множество различных способов решения этой проблемы, вот несколько различных подходов.

Подход 1: Для петель

# Initialize a list
primes = []

for possiblePrime in range(2, 21):
    
    # Assume number is prime until shown it is not. 
    isPrime = True
    for num in range(2, possiblePrime):
        if possiblePrime % num == 0:
            isPrime = False
      
    if isPrime:
        primes.append(possiblePrime)

Если вы посмотрите на внутренний цикл for, заключенный в красный прямоугольник ниже, обратите внимание, что, как только isPrime имеет значение False, продолжать итерацию неэффективно. Было бы более эффективно выйти из цикла.

Подход 2: Для петель с разрывом

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

# Initialize a list
primes = []
for possiblePrime in range(2, 21):
    
    # Assume number is prime until shown it is not. 
    isPrime = True
    for num in range(2, possiblePrime):
        if possiblePrime % num == 0:
            isPrime = False
            break
      
    if isPrime:
        primes.append(possiblePrime)

Подход 2 гораздо более эффективен, чем подход 1. Например, если вы посмотрите на случай , когда возможное простое число , обратите внимание, что в подходе 2 гораздо меньше итераций.

Подход 3: Для цикла, разрыва и квадратного корня

Подход 2 выиграл от того, что не делал ненужных итераций во внутреннем цикле for. Подход 3 аналогичен, за исключением функции внутреннего диапазона. Обратите внимание, что функция внутреннего диапазона теперь range(2, int(возможное простое число ** 0.5) + 1) .

# Initialize a list
primes = []
for possiblePrime in range(2, 21):
    
    # Assume number is prime until shown it is not. 
    isPrime = True
    for num in range(2, int(possiblePrime ** 0.5) + 1):
        if possiblePrime % num == 0:
            isPrime = False
            break
      
    if isPrime:
        primes.append(possiblePrime)

Чтобы объяснить, почему этот подход работает, важно отметить несколько вещей. Составное число-это положительное число, большее 1, которое не является простым (которое имеет факторы , отличные от 1 и самого себя). Каждое составное число имеет коэффициент, меньший или равный его квадратному корню (доказательство здесь ). Например, на изображении факторов 15 ниже обратите внимание, что факторы, выделенные красным цветом, являются просто обратными зеленым факторам. Другими словами, коммутативным свойством умножения 3 x x 3. Вам просто нужно включить зеленые пары, чтобы убедиться, что у вас есть все факторы.

Коэффициенты 15

Сравнение во времени различных подходов

Некоторые методы генерации простых чисел более эффективны. Чтобы показать это, давайте изучим разницу в производительности между подходами, генерирующими простые числа до заданного числа.

Подход 1: Для петель

def approach1(givenNumber):
     # Initialize a list
    primes = []
    
    for possiblePrime in range(2, givenNumber + 1):
        # Assume number is prime until shown it is not. 
        isPrime = True
        for num in range(2, possiblePrime):
            if possiblePrime % num == 0:
                isPrime = False
        if isPrime:
            primes.append(possiblePrime)
    return(primes)

Подход 2: Для петель с разрывом

def approach2(givenNumber):
    # Initialize a list
    primes = []
    
    for possiblePrime in range(2, givenNumber + 1):
        # Assume number is prime until shown it is not. 
        isPrime = True
        for num in range(2, possiblePrime):
            if possiblePrime % num == 0:
                isPrime = False
                break
        if isPrime:
            primes.append(possiblePrime)
    
   return(primes)

Подход 3: Для цикла, разрыва и квадратного корня

def approach3(givenNumber):  
    # Initialize a list
    primes = []
    
    for possiblePrime in range(2, givenNumber + 1):
        # Assume number is prime until shown it is not. 
        isPrime = True
        for num in range(2, int(possiblePrime ** 0.5) + 1):
            if possiblePrime % num == 0:
                isPrime = False
                break
        if isPrime:
            primes.append(possiblePrime)
    
    return(primes)

Разница в производительности может быть измерена с помощью библиотеки timeit , которая позволяет вам синхронизировать код Python. В этом случае мы измеряем время, необходимое для нахождения простых чисел до 500 для каждого подхода. Приведенный ниже код запускает код для каждого подхода 10000 раз и выводит общее время, которое потребовалось в секундах.

import timeit

# Approach 1: Execution time 
print(timeit.timeit('approach1(500)', globals=globals(), number=10000))

# Approach 2: Execution time
print(timeit.timeit('approach2(500)', globals=globals(), number=10000))

# Approach 3: Execution time
print(timeit.timeit('approach3(500)', globals=globals(), number=10000))

Очевидно, что подход 3 является самым быстрым.

Заключительные замечания

Эти три подхода, безусловно, не являются единственными способами вычисления простых чисел, но, надеюсь, различные способы идентификации простых чисел помогли вам. Простые числа важны в теории чисел и криптографических методах, таких как алгоритм rsa. Как всегда, код в посте также доступен на моем github ( код подхода , сравнение времени ). Если у вас есть какие-либо вопросы или мысли по учебнику, не стесняйтесь обращаться к нам в комментариях ниже или через Twitter .

Эта статья первоначально появилась в моем блоге medium