Программа Python для проверки того, является ли число простым или нет - UPROGER

Факторы числа:

Когда два целых числа умножаются, получается произведение. Факторы продукта – это числа, которые мы умножаем.

В математике коэффициент – это число или алгебраическое выражение, которое поровну делит другое число или выражение, не оставляя остатка.

Простое число:

Простое число – это положительное целое число больше 1, не имеющее других переменных, кроме 1 и самого числа. Поскольку у них нет других переменных, числа 2, 3, 5, 7 и т. Д. Являются простыми числами.

Учитывая число, задача состоит в том, чтобы проверить, является ли данное число простым или нет.

Примеры:

Пример 1:

Вход:

number =5

Выход:

The given number 5 is a prime number

Пример 2:

Вход:

number =2

Выход:

The given number 2 is not prime number

Программа для проверки простого числа в программировании на Python

Ниже приведены способы проверить, является ли данное число простым или нет:

Изучите больше примеров, связанных с концепциями Python, из Руководства по примерам программирования Python и получите повышение от новичка до профессионального уровня программиста в языке программирования Python.

1) Использование цикла for для перехода от 2 к N-1 с использованием флаговой или временной переменной

Чтобы увидеть, есть ли какие-либо положительные делители, кроме 1 и самого числа, мы делим входное число на все числа в диапазоне от 2 до (N – 1).

Если делитель найден, отображается сообщение «число не является простым числом», в противном случае отображается сообщение «число является простым числом».

Мы выполняем итерацию от 2 до N-1, используя цикл for.

Ниже представлена реализация:

# given number
number = 5
# intializing a temporary variable with False
temp = False
# We will check if the number is greater than 1 or not
# since prime numbers starts from 2
if number > 1:
    # checking the divisors of the number
    for i in range(2, number):
        if (number % i) == 0:
            # if any divisor is found then set temp to true since it is not prime number
            temp = True
            # Break the loop if it is not prime
            break
if(temp):
    print("The given number", number, "is not prime number")
else:
    print("The given number", number, "is prime number")

Выход:

The given number 5 is prime number

Объяснение:

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

Мы проверяем, делится ли число в точности на любое число от 2 до числа – 1. Мы устанавливаем temp равным True и прерываем цикл, если найдем множитель в этом диапазоне, указывающий, что число не является простым.

Мы проверяем, является ли temp истинным или ложным вне цикла.

Число не является простым числом, если оно истинно.
Если False, данное число является простым числом.

2) Использование оператора For Else

Чтобы проверить, является ли число простым, мы использовали аргумент for… else.

Он основан на логике, согласно которой оператор else цикла for выполняется тогда и только тогда, когда цикл for не прерывается. Только когда переменные не найдены, выполняется условие, указывающее, что данное число является простым.

В результате мы печатаем, что число простое в предложении else.

Ниже представлена реализация:

# given number
number = 5

# We will check if the number is greater than 1 or not
# since prime numbers starts from 2
if number > 1:
    # checking the divisors of the number
    for i in range(2, number):
        if (number % i) == 0:
            # if any divisor is found then print it is not prime
            print("The given number", number, "is not prime number")
            # Break the loop if it is not prime
            break
    else:
        print("The given number", number, "is prime number")
# if the number is less than 1 then print it is not prime number
else:
    print("The given number", number, "is not prime number")

Выход:

The given number 5 is prime number

3) Ограничения вышеперечисленных методов с точки зрения временной сложности

В этих двух методах цикл идет от 2 до номера N-1.

Следовательно, мы можем сказать, что временная сложность вышеупомянутых методов составляет O (n).

Что делать, если число очень большое?

Как и 10 ^ 18, выполнение вышеуказанных методов занимает почти 31 год.

Тогда как этого избежать?

Мы видим, что множители чисел существуют от 1 до N / 2, за исключением самого числа.

Но это также занимает около 15 лет.

Таким образом, мы выполняем цикл до квадратного корня из N в следующем методе, который дает временную сложность O (Sqrt (n)).

4) Подход к решению для эффективного подхода

Мы улучшим нашу программу, сократив диапазон чисел, в котором мы ищем факторы.

Наш диапазон поиска в приведенной выше программе – от 2 до числа – 1.

Должен был использоваться набор, диапазон (2, число / 2) или диапазон (2, math.floor (math.sqrt (число)). Последний диапазон основан на требовании, чтобы коэффициент составного числа был меньше его квадрата. корень. В противном случае это простое число.

5) Внедрение эффективного подхода

В этой функции мы используем математическую библиотеку Python для вычисления целого числа max_divisor, которое является квадратным корнем из числа, и получения его минимального значения. В последнем примере мы выполняем итерацию от 2 до n-1. Однако в этом случае мы уменьшаем делители вдвое, как показано. Чтобы получить функции floor и sqrt, вам необходимо импортировать модуль math.
Подход:

Если целое число меньше единицы, возвращается False.
Числа, которые необходимо проверить, теперь уменьшаются до квадратного корня из заданного числа.
Функция вернет False, если данное число делится на любое из чисел от 2 до квадратного корня из числа.
В противном случае будет возвращено True.

Ниже представлена реализация:

# importing math module
import math
# function which returns True if the number is prime else not


def checkPrimeNumber(number):
    if number < 1:
        return False
    # checking the divisors of the number
    max_divisor = math.floor(math.sqrt(number))
    for i in range(2, max_divisor+1):
        if number % i == 0:
            # if any divisor is found then return False
            return False
        # if no factors are found then return True
        return True


# given number
number = 5
# passing number to checkPrimeNumber function
if(checkPrimeNumber(number)):
    print("The given number", number, "is prime number")
else:
    print("The given number", number, "is not prime number")

Выход: