Задача 6

Условия задачи:

1. Изучите тему и напишите другой способ нахождения простых чисел.

Решение задачи:

#1
def main():
    def is_prime(value):
        if value != 1:
            if value != 2 and value != 3 and value != 5 and value != 7:
                if value % 2 != 0 and value % 3 != 0 and value % 5 != 0 and value % 7 != 0:
                    return True
                else:
                    return False
            else:
                return True
        else:
            pass
    num = int(input('Введите целое число: '))
    if is_prime(num):
        print(f'{num} - это простое число')
    else:
        print(f'{num} - это непростое число')
#2 
def is_prime_naive(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

#3
def is_prime_optimized(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True
#4
def sieve_of_eratosthenes(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            sieve[i*i : n+1 : i] = [False] * len(sieve[i*i : n+1 : i])
    return [i for i, prime in enumerate(sieve) if prime]