Рубрики

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

Учитывая положительное целое число, проверьте, является ли число простым или нет. Простое число — это натуральное число, большее 1, которое не имеет положительных делителей, кроме 1 и самого себя. Примеры первых нескольких простых чисел: {2, 3, 5,

Примеры:

Input:  n = 11
Output: true

Input:  n = 15
Output: false

Input:  n = 1
Output: false

Школьный метод:

# Школьный метод на основе Python3
# программа для проверки номера
# простое

  

def isPrime(n):

  

    # Угловой кейс

    if n <= 1:

        return False

  

    # Проверка от 2 до n-1

    for i in range(2, n):

        if n % i == 0:

            return False;

  

    return True

  
Программа # Driver для проверки вышеуказанной функции

print("true") if isPrime(11) else print("false")

print("true") if isPrime(14) else print("false")

  
# Этот код предоставлен Смитой Динеш Семвал

Выход:

true
false

Временная сложность этого решения составляет O (n)

Оптимизированный школьный метод:

# Оптимизированный школьный метод на основе
# Python3 программа для проверки
# если число простое

    

    

def isPrime(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 = i + 6

    

    return True

    

    
# Драйверная программа

    

if(isPrime(11)) : 

    print(" true"

else

    print(" false"

        

if(isPrime(15)) : 

    print(" true"

else :  

    print(" false"

        

        
# Этот код добавлен
# Никита Тивари.

Выход:

true
false

Пожалуйста, обратитесь полную статью о тесте Primality | Установите 1 (Введение и школьный метод) для более подробной информации!

Рекомендуемые посты:

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

0.00 (0%) 0 votes