Нужно найти ближайший ближайший простое число на python в основных терминах - PullRequest
Новая
       21

Нужно найти ближайший ближайший простое число на python в основных терминах

0 голосов
/ 09 ноября 2019

Я новичок в Python, и мне нужно попросить пользователя ввести число n и вывести простое число, ближайшее к n.

Если есть два простых числа, одинаково близких к n, выведите меньшееиз двух.

, например: введите n: 17. Самое близкое к 17 число равно 17, введите n: 6 Самое близкое к 6 число равно 5

Я не могу использовать сложные коды, поэтому, пожалуйста,Помощь - это самый простой способ!

* Более подробно, я ничего не пробовал, так как даже не знаю, с чего начать! Мне сказали написать код, который проверяет, является ли число, например K, простым или нет, помещать этот код в цикл, который начинается с K, и продолжает увеличиваться, пока не найдет простое число. Затем сделайте то же самое, но вниз. Надеюсь, это поможет

1 Ответ

0 голосов
/ 13 ноября 2019

Сито кажется правильным подходом, в отличие от алгоритма, описанного в ОП. Если мы просеем до n и n - простое, мы закончили. Если нет, нам нужно только найти первое простое число после n, а затем мы знаем ответ. Поскольку 2 всегда является наихудшим ответом, нам не нужно просеивать дальше 2 * n. И, поскольку мы находим растущие простые числа менее чем n, мы можем уменьшить размер нашего сита, уменьшая количество ударов, которое нам нужно сделать. Вот мой неоптимизированный пример решения этой проблемы: 

def closest_prime(n):
    if n <= 1:  # handle 0 & 1 as special cases
        return 2

    sieve_limit = 2 * n

    sieve = [False, False] + [True] * (sieve_limit - 2)

    prime_candidate = number = 2

    while number < sieve_limit:
        if sieve[number]:
            if number == n:
                return n  # n is prime

            if number > n:
                if (number - n) < (n - prime_candidate):
                    return number

                return prime_candidate

            prime_candidate = number

            sieve_limit = 2 * n - prime_candidate  # reduce sieve size

            for index in range(number * number, sieve_limit, number):
                sieve[index] = False

        number += 1

    return prime_candidate  # ran off end of sieve

if __name__ == "__main__":
    print(20831428, closest_prime(20831428))
    print(20831429, closest_prime(20831429))

ВЫВОД 

> python3 test.py
20831428 20831323
20831429 20831533
>

Я выбрал приведенный выше тестовый пример, поскольку между 209простые числа 20831323 и 20831533. Код, приведенный в комментариях, не обрабатывает второй тест правильно, так как использует верхний предел сита с жестким кодом. Как я уже отмечал выше, этот код не оптимизирован, например:

  • Мы можем быть умнее с четными числами, чтобы уменьшить количество проверок и ударов.

  • Мы можем отрегулировать предел сита на один или около того, так как в случае связи мы возьмем нижнее простое число.

  • Если n - 1 простое число, мы можем просто вернутьчто если n не простое число, а даже не искать первое простое число выше n.

...