Dado un número entero positivo N, la tarea es escribir un programa Python para verificar si el número es Principal o no en Pitón .

multiplexor

Ejemplos:

  Input:   n = 11   Output:   True   Input:   n = 1   Output:   False   Explanation:   A prime number is a natural number greater than 1 that  has no positive divisors other than 1 and itself.  The first few prime numbers are {2, 3, 5, 7, 11, ….}.>

Programa Python para verificar números primos

La idea para resolver este problema es iterar a través de todos los números comenzando desde 2 hasta (N/2) usando un en bucle y para cada número verificamos si divide a N. Si encontramos algún número que divide, devolvemos falso. Si no encontramos ningún número entre 2 y N/2 que divida a N, significa que N es primo y devolveremos Verdadero.

num = 11 # If given number is greater than 1 if num>1: # Iterar de 2 a n // 2 para i en rango(2, (num//2)+1): # Si num es divisible por cualquier número entre # 2 y n / 2, no es primo si ( num % i) == 0: print(num, 'no es un número primo') break else: print(num, 'es un número primo') else: print(num, 'no es un número primo número')>

11 is a prime number>

Complejidad del tiempo : En)
Espacio auxiliar: O(1)

Encuentra números primos con una variable de bandera

En lugar de verificar hasta n, podemos verificar hasta √n porque un factor mayor de n debe ser múltiplo de un factor menor que ya ha sido verificado. Ahora veamos el código para el primer método de optimización (es decir, verificar hasta √n).

from math import sqrt # n is the number to be check whether it is prime or not n = 1 # this flag maintains status whether the n is prime or not prime_flag = 0 if(n>1): para i en rango(2, int(sqrt(n)) + 1): if (n % i == 0): prime_flag = 1 break if (prime_flag == 0): print('True' ) más: imprimir('Falso') más: imprimir('Falso')>

False>

Complejidad del tiempo :O(sqrt(n))
Espacio auxiliar: O(1)

Verificar números primos mediante recursividad

También podemos encontrar el número primo o no usando recursividad . Podemos usar la lógica exacta que se muestra en el método 2 pero de forma recursiva.

algoritmo rr

from math import sqrt def Prime(number,itr): #prime function to check given number prime or not if itr == 1: #base condition return True if number % itr == 0: #if given number divided by itr or not return False if Prime(number,itr-1) == False: #Recursive function Call return False return True num = 13 itr = int(sqrt(num)+1) print(Prime(num,itr))>

True>

Complejidad del tiempo: O(sqrt(n))
Espacio auxiliar :O(sqrt(n))

Consulte el método de la división de prueba principal

def is_prime_trial_division(n): # Check if the number is less than # or equal to 1, return False if it is if n <= 1: return False # Loop through all numbers from 2 to # the square root of n (rounded down to the nearest integer) for i in range(2, int(n**0.5)+1): # If n is divisible by any of these numbers, return False if n % i == 0: return False # If n is not divisible by any of these numbers, return True return True # Test the function with n = 11 print(is_prime_trial_division(11))>

True>

Complejidad del tiempo: O (sqrt (n))
Espacio auxiliar: O(sqrt(n))

Artículo recomendado – Análisis de diferentes métodos para encontrar números primos en Python

Programa Python para verificar números primos usando un bucle while para verificar la divisibilidad

Inicialice una variable i en 2. Mientras i al cuadrado sea menor o igual que n, verifique si n es divisible por i. Si n es divisible por i, devuelve False. De lo contrario, incremente i en 1. Si el ciclo finaliza sin encontrar un divisor, devuelve Verdadero.

actualizar desde unirse a sql

import math def is_prime(n): if n < 2: return False i = 2 while i*i <= n: if n % i == 0: return False i += 1 return True print(is_prime(11)) # True print(is_prime(1)) # False>

True False>

Complejidad del tiempo: O(sqrt(n))
Espacio auxiliar: O(1)

Programa Python para verificar números primos usando el módulo de matemáticas

El código implementa un enfoque básico para verificar si un número es primo o no, recorriendo todos los números desde 2 hasta sqrt(n)+1 y verificando si n es divisible por alguno de esos números.

import math def is_prime(n): if n <= 1: return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True n = 11 print(is_prime(n))>

True>

Complejidad del tiempo: O(sqrt(n))
La complejidad temporal del código es O(sqrt(n)) porque atravesamos todos los números en el rango de 2 a sqrt(n)+1 para verificar si n es divisible por alguno de ellos.

entidad relacional

Espacio Auxiliar: O(1)
La complejidad espacial del código es O(1) porque solo usamos una cantidad constante de memoria para almacenar el número de entrada n y las variables del bucle.

Programa Python para verificar números primos usando el método sympy.isprime()

En el módulo Sympy, podemos probar si un número dado n es primo o no usando la función sympy.isprime(). Para norte <2⁶⁴la respuesta es definitiva; Los valores de n más grandes tienen una pequeña probabilidad de ser pseudoprimos.

NÓTESE BIEN.: Los números negativos (por ejemplo, -13) no se consideran números primos.

# Python program to check prime number # using sympy.isprime() method # importing sympy module from sympy import * # calling isprime function on different numbers geek1 = isprime(30) geek2 = isprime(13) geek3 = isprime(2) print(geek1) # check for 30 is prime or not print(geek2) # check for 13 is prime or not print(geek3) # check for 2 is prime or not # This code is contributed by Susobhan Akhuli>

Producción

False True True>

Complejidad del tiempo: O(sqrt(n)), donde n es el número de entrada.
Espacio Auxiliar: O(1)