primes.py - master - mserg54/Test

primes.py
134 строки5 KB
Михаил Сергеев
пробные программы python
10 апр 2026, 00:12
10 апр 2026, 00:12c4c6326
#!/usr/bin/env python3
"""
Программа для вычисления заданного количества простых чисел
"""
import time
from typing import List

def is_prime(n: int) -> bool:
    """Проверить, является ли число простым."""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # Проверяем делители до квадратного корня
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

def generate_primes(count: int) -> List[int]:
    """Сгенерировать заданное количество простых чисел."""
    if count <= 0:
        return []
    
    primes = []
    num = 2
    
    while len(primes) < count:
        if is_prime(num):
            primes.append(num)
        num += 1
    
    return primes

def sieve_of_eratosthenes(limit: int) -> List[int]:
    """Найти все простые числа до заданного предела с помощью решета Эратосфена."""
    if limit < 2:
        return []
    
    # Создаем список, где индекс соответствует числу
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False  # 0 и 1 не являются простыми
    
    for i in range(2, int(limit ** 0.5) + 1):
        if sieve[i]:
            # Помечаем кратные i как составные
            for j in range(i * i, limit + 1, i):
                sieve[j] = False
    
    return [i for i in range(2, limit + 1) if sieve[i]]

def generate_primes_optimized(count: int) -> List[int]:
    """Сгенерировать заданное количество простых чисел с оптимизацией."""
    if count <= 0:
        return []
    
    if count == 1:
        return [2]
    
    # Оценка верхней границы по теореме о распределении простых чисел
    # Для n > 5: n * (log(n) + log(log(n))) является хорошей оценкой
    import math
    if count < 6:
        limit = 12  # Минимальный разумный предел
    else:
        limit = int(count * (math.log(count) + math.log(max(1, math.log(count)))))
    
    # Увеличиваем предел, если недостаточно простых чисел
    while True:
        primes = sieve_of_eratosthenes(limit)
        if len(primes) >= count:
            return primes[:count]
        limit = int(limit * 1.5)  # Увеличиваем предел и пробуем снова

def main():
    """Главная функция программы."""
    print("Расчет простых чисел")
    print("==================")
    
    while True:
        try:
            count = int(input("\nВведите количество простых чисел для вычисления (0 для выхода): "))
            
            if count == 0:
                print("До свидания!")
                break
            
            if count < 0:
                print("Пожалуйста, введите положительное число.")
                continue
            
            print(f"\nПоиск первых {count} простых чисел...")
            start_time = time.time()
            
            # Используем оптимизированный метод для больших значений
            if count > 1000:
                primes = generate_primes_optimized(count)
                method = "решето Эратосфена (оптимизированное)"
            else:
                primes = generate_primes(count)
                method = "последовательная проверка"
            
            end_time = time.time()
            
            print(f"\nНайдено {len(primes)} простых чисел с использованием метода '{method}':")
            
            # Выводим результаты
            if count <= 20:
                print(" ".join(map(str, primes)))
            elif count <= 100:
                # Выводим по 10 чисел в строке
                for i in range(0, len(primes), 10):
                    print(" ".join(map(str, primes[i:i+10])))
            else:
                # Для больших количеств выводим только первые и последние 10
                print("Первые 10: ", " ".join(map(str, primes[:10])))
                print("...")
                print("Последние 10: ", " ".join(map(str, primes[-10:])))
            
            print(f"\nВремя выполнения: {end_time - start_time:.4f} секунд")
            
        except ValueError:
            print("Пожалуйста, введите корректное целое число.")
        except KeyboardInterrupt:
            print("\n\nПрограмма прервана пользователем.")
            break
        except Exception as e:
            print(f"Произошла ошибка: {e}")

if __name__ == "__main__":
    main()