Блог

Главная - Python язык программирования - Программа на Python для проверки того, является ли число простым или нет
You are currently viewing Программа на Python для проверки того, является ли число простым или нет

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

Учитывая положительное целое число N, задача состоит в том, чтобы написать программу на Python, чтобы проверить, является ли это число основной или нет.
Определение: Простое число-это натуральное число, большее 1, у которого нет положительных делителей, кроме 1 и самого себя. Первые несколько простых чисел {2, 3, 5, 7, 11, ….}.

Примеры :

Input: n = 11
Output: true

Input: n = 15
Output: false

Input: n = 1
Output: false

Идея решения этой проблемы состоит в том, чтобы повторить все числа, начиная с 2 до (N/2), используя цикл for, и для каждого числа проверить, разделяет ли оно N. Если мы найдем любое число, которое делится, мы вернем false. Если мы не нашли никакого числа между 2 и N/2, которое делит N, то это означает, что N-простое число, и мы вернем True.

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

# Python program to check if
# given number is prime or not

num = 11

# If given number is greater than 1
if num > 1:

	# Iterate from 2 to n / 2
	for i in range(2, int(num/2)+1):

		# If num is divisible by any number between
		# 2 and n / 2, it is not prime
		if (num % i) == 0:
			print(num, "is not a prime number")
			break
	else:
		print(num, "is a prime number")

else:
	print(num, "is not a prime number")

Выход:

11 is a prime number

Оптимизированный Способ
Мы можем выполнить следующие оптимизации:

Вместо того, чтобы проверять до n, мы можем проверять до √n, потому что больший фактор n должен быть кратен меньшему фактору, который уже был проверен.

Теперь давайте посмотрим код первого метода оптимизации ( т. е. Проверим до √n )

from math import sqrt
# n is the number to be check whether it is prime or not
n = 1

# no lets check from 2 to sqrt(n)
# if we found any facto then we can print as not a prime number

# this flag maintains status whether the n is prime or not
prime_flag = 0

if(n > 1):
	for i in range(2, int(sqrt(n)) + 1):
		if (n % i == 0):
			prime_flag = 1
			break
	if (prime_flag == 0):
		print("true")
	else:
		print("false")
else:
	print("false")

Выход:

Алгоритм можно дополнительно улучшить, заметив, что все простые числа имеют вид 6k ± 1, за исключением 2 и 3. Это связано с тем, что все целые числа могут быть выражены как (6k + i) для некоторого целого числа k и для i = -1, 0, 1, 2, 3, или 4; 2 деления (6k + 0), (6k + 2), (6k + 4); и 3 деления (6k + 3). Таким образом, более эффективный метод состоит в том, чтобы проверить, делится ли n на 2 или 3, а затем проверить все числа формы 6k ± 1.

Метки: ,