Простые числа

Простое число — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя.

Для проверки является ли конкретное число простым проверим это перебрав все его делители. Данный алгоритм называется проверкой на простоту перебором делителей.

def isprime(n):
    if n == 1:
        return False   
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

Если нам нужно найти простые числа в каком-то диапозоне, то существуют алгоритмы нахождения списка простых чисел от 2 до некоторого значения:

1. Решето Эратосфена
2. Решето Сундарама
3. Решето Аткина

Задача 1. Простые числа. |Теория чисел|

Выведите все простые чила от M до N включительно. Если между ними нет простых чисел выведите "Absent".

Решение:

import math
m = int(input()) # первое число
n = int(input()) # второе число
k = math.ceil(math.sqrt(n))
x = m
isAbsent = True
isPrime = True
while x <= n:
    count = 2
    while count <= k and isPrime:
        if x % count == 0: 
            isPrime = False
        count = count + 1
    if isPrime: 
        print(x)
        isAbsent = False
    isPrime = True
    x = x + 1
if isAbsent: print('Absent')

Алгоритм нахождения всех простых чисел от 2 до N при помощи множеств

def primes(N):
    """Возвращает все простые числа от 2 до N"""
    sieve = set(range(2, N))
    for i in range(2, int(math.sqrt(N)) + 1):
        if i in sieve:    
            sieve -= set(range(2 * i, N, i))
    return sieve

Задача 2. Разложение на простые множители. |Теория чисел|

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

Задача 3. Совершенные числа. |Теория чисел|

Задача 4. Дружественные числа. |Теория чисел|