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

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

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

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

Начнем с определения простого числа. Простые числа — это положительные целые числа больше 1, которые делятся только на себя и на 1 без остатка. Например, 2, 3, 5 и 7 являются примерами простых чисел. Числа, не являющиеся простыми, кроме 1, называются составными числами. Тогда читатель может спросить: является ли число 1 ни простым, ни составным? Ответ положительный. 1 не является ни простым, ни составным числом.

Теперь давайте напишем функцию, которая проверяет, является ли число простым или нет. Назовем нашу функцию is_prime. Поскольку функция проверяет, является ли заданное целое число простым, она имеет один аргумент. Обозначим этот аргумент через n. Теперь нам нужно написать цикл, чтобы проверить, делится ли n на все целые числа от 2 до n-1. Если оно хотя бы делится на одно из них, а именно является составным, то функция возвращает False. Но если условие делимости не выполняется ни для одного целого числа в цикле, а именно, n простое число; то функция возвращает True.

def is_prime(n):
    for i in range(2,n):
        if n % i == 0:
            return False
    return True

Теперь давайте сделаем следующее наблюдение, которое станет основой решетчатого метода Эратосфена:

Если целое число составное, то его делитель меньше или равен его квадратному корню.

Доказательство. Предположим, n — составное число. Мы хотим показать, что у n есть делитель, меньший или равный его квадратному корню. Поскольку «n» — составное число, по определению существует положительное целое число «a» между 1 и n. Тогда мы можем написать, что «n=a.b», где a и b — два положительных целых числа, отличных от 1 и n. Предположим, что наша цель, состоящая в том, чтобы доказать, что n имеет делитель, меньший или равный его квадратному корню, неверна. Итак, все делители n больше его квадратного корня. В частности, a и b больше квадратного корня из n. Но это дает следующее противоречие:

Следовательно, утверждение, что все делители числа n больше его квадратного корня, неверно. Другими словами, у n есть делитель, меньший или равный его квадратному корню.

Используя это наблюдение, давайте посмотрим, как работает Решето Эратосфена. Попробую объяснить на примере. Например, мы хотим перечислить простые числа меньше 100. Для этого сначала создадим список всех положительных целых чисел от 2 до 100. Затем мы удалим из этого списка составные числа. Как мы заметили выше, если число из этого списка составное, оно должно иметь делитель, меньший или равный квадратному корню из 100. Поэтому, если мы хотим исключить составные числа, достаточно удалить числа из списка которые кратны числам меньше 10. В конечном итоге мы получим список только простых чисел меньше 100.

Давайте напишем функцию, которая использует этот метод и удаляет составные числа из списка. Во-первых, нам нужно импортировать библиотеку с именем math. Определим нашу функцию как EratosthenesSieve. Поскольку эта функция возвращает список всех простых чисел, меньших заданного числа, она имеет параметр N целочисленного типа. В теле мы сначала создаем список чисел, содержащий все целые числа от 2 до N. Затем нам нужен цикл по простым числам от 2 до квадратного корня из N. В этом цикле мы присваиваем 2 раза соответствующее простое число число в переменную, называемую пробной. Пока эта новая пробная переменная меньше N и находится в списке чисел, мы удаляем ее из списка и сразу после этого обновляем пробную переменную как 3-кратное соответствующее простое число. Мы удаляем его, если он все еще меньше N и находится в списке чисел. Продолжая таким образом до тех пор, пока кратное соответствующему простому числу не станет больше N, давайте перейдем к следующему простому числу и повторим тот же процесс. Давайте раскроем здесь скобки. Например, когда мы удаляем из списка 3 раза по 2, 2 раза по 3 уже удалены из списка. Следовательно, нам нужно проверить, есть ли переменная trial в списке чисел, чтобы не повторять этот процесс. По завершении цикла функция eratosthenesSieve возвращает оставшийся список. Это список, содержащий все простые числа, меньшие N.

def eratosthenesSieve(N):
    numbers = list(range(2, N+1))
    for p in range(2, int(math.sqrt(N) + 1)):
        if is_prime(p):
            trial = p * 2
            while trial <= N:
                if trial in numbers:
                    numbers.remove(trial)
                trial += p
    return numbers

Пришло время для последнего приложения в этом посте. Как я упоминал в начале, я хочу определить функцию, которая дает простую факторизацию положительного целого числа. Однако, прежде чем создавать эту функцию, давайте откроем еще одну скобку и поговорим об основной теореме арифметики, которая является одним из самых значительных результатов в теории чисел. Теорема утверждает, что любое целое число больше 1 может быть однозначно представлено в виде произведения простых чисел с точностью до порядка множителей. Например, 100 можно представить как произведение простых чисел 2 и 5 независимо от порядка следующим образом:

100 = 2.2.5.5

Давайте определим функцию, которая возвращает эту простую факторизацию. Пусть его имя будет get_primes_factor. У него есть параметр N целочисленного типа, так как это функция, которая дает простую факторизацию положительного целого числа. В теле мы сначала создаем пустой список с именем prime_factors. Наша цель — заполнить этот список простыми делителями числа N. Для этого; мы суммируем возможные числа из списка prime_factors, используя нашу предыдущую функцию eratosthenesSieve(). Давайте вызовем функцию EratosthenesSieve(), а затем назначим результат функции списку кандидатов_простых чисел. Ясно, что этот список состоит из простых чисел, меньших N. Теперь мы хотим проверить, делятся ли эти простые числа на N и сколько раз они делятся, перебирая элементы этого списка кандидатов_простых. Если соответствующее простое число в цикле делит N, добавим его в список prime_factors. Если он продолжает делить N, мы продолжаем добавлять в список. Когда цикл завершится, в списке prime_factors появится простая факторизация числа N. Ради привлекательности выведем на экран простую факторизацию N.

def get_primes_factor(N):
    print(N, '=', end = ' ')
    prime_factors = []
    candidate_primes = eratosthenesSieve(N)
    for prime in candidate_primes:
        while N % prime == 0:
            prime_factors.append(prime)
            N //= prime
    print(*prime_factors, sep='.')

Надеюсь, я не сделал этот первый пост слишком скучным из-за слишком большого количества математики. Я надеюсь, что это было несколько приятных приложений для тех, кто больше интересуется математикой, особенно теорией чисел. Пока писал пост, в голову пришло много новых приложений, но я остановил себя. Как я уже сказал, это будет серия, объясняющая процесс науки о данных с точки зрения математика. Возможно, в другом посте мы будем использовать эти функции для анализа простых чисел в наборе данных и лучше прочувствуем некоторые из самых замечательных результатов в теории чисел.

Для тех, кто хочет попробовать, вы можете создать метод простого сита, используя функцию is.prime(). Если сравнить это сито с ситом Эратосфена, какое из них более эффективно?