logo

TechCodeview

Números primos

¿Qué son los números primos?

A número primo se define como un número natural mayor que 1 y es divisible sólo por 1 y por sí mismo.

En otras palabras, el número primo es un número entero positivo mayor que 1 que tiene exactamente dos factores, 1 y el número mismo. Los primeros números primos son 2, 3, 5, 7, 11, 13, 17, 19, 23. . .



Nota: 1 no es primo ni compuesto. El resto de los números, excepto el 1, se clasifican en números primos y compuestos.

números primos

Algunos datos interesantes sobre los números primos:

  • Excepto 2 que es el más pequeño número primo y el único número primo par, todos los números primos son números impares.
  • Todo número primo se puede representar en forma de 6norte + 1 o 6n – 1 excepto los números primos 2 y 3 , donde n es cualquier número natural.
  • 2 y 3 Sólo hay dos números naturales consecutivos que son primos.
  • Conjetura de Goldbach: Todo número par mayor que 2 se puede expresar como la suma de dos números primos.
  • Teorema de Wilson : El teorema de Wilson establece que un número natural p> 1 es un número primo si y sólo si

(página – 1) ! ≡ -1 contra p
O,
(página – 1) ! ≡ (p-1) mod p



an-1≡ 1 (mód n)
O,
an-1% norte = 1

  • Teorema de los números primos : La probabilidad de que un número n dado, elegido al azar, sea primo es inversamente proporcional a su número de dígitos, o al logaritmo de n.
  • La conjetura de Lemoine : Cualquier número entero impar mayor que 5 se puede expresar como la suma de un primo impar (todos los primos distintos de 2 son impares) y un semiprimo par. Un número semiprimo es el producto de dos números primos. Esto se llama conjetura de Lemoine.

Propiedades de los números primos:

  • Todo número mayor que 1 se puede dividir por al menos un número primo.
  • Todo número entero positivo par mayor que 2 se puede expresar como la suma de dos números primos.
  • Excepto 2, todos los demás números primos son impares. En otras palabras, podemos decir que 2 es el único número primo par.
  • Dos números primos siempre son coprimos entre sí.
  • Cada número compuesto se puede descomponer en factores primos e individualmente, todos ellos son únicos por naturaleza.

Números primos y números coprimos:

Es importante distinguir entre números primos y números coprimos . A continuación se enumeran las diferencias entre números primos y coprimos.

  • Los números coprimos siempre se consideran un par, mientras que un número primo es un número único.
  • Los números coprimos son números que no tienen factor común excepto 1. Por el contrario, los números primos no tienen tal condición.
  • Un número coprimo puede ser primo o compuesto, pero su máximo común divisor (MCD) siempre debe ser 1. A diferencia de los números compuestos, los números primos solo tienen dos factores, 1 y el número mismo.
  • Ejemplo de coprincipal: 13 y 15 son coprimos. Los factores de 13 son 1 y 13 y los factores de 15 son 1, 3 y 5. Podemos ver que tienen solo 1 como factor común, por lo tanto, son números coprimos.
  • Ejemplo de prima: Algunos ejemplos de números primos son 2, 3, 5, 7 y 11, etc.

¿Cómo comprobar si un número es Prime o no?

Enfoque ingenuo: El enfoque ingenuo es



Itere de 2 a (n-1) y verifique si algún número en este rango se divide norte . si el numero se divide norte , entonces no es un número primo.

Complejidad del tiempo: EN)
Espacio Auxiliar: O(1)

Enfoque ingenuo (recursivo): La recursividad también se puede utilizar para comprobar si un número entre 2 a n – 1 divide n. Si encontramos algún número que divida, devolvemos falso.

A continuación se muestra la implementación de la idea anterior:

C++




// C++ program to check whether a number> // is prime or not using recursion> #include> using> namespace> std;> > // function check whether a number> // is prime or not> bool> isPrime(>int> n)> {> >static> int> i = 2;> > >// corner cases> >if> (n == 0 || n == 1) {> >return> false>;> >}> > >// Checking Prime> >if> (n == i)> >return> true>;> > >// base cases> >if> (n % i == 0) {> >return> false>;> >}> >i++;> >return> isPrime(n);> }> > // Driver Code> int> main()> {> > >isPrime(35) ? cout <<>' true '> : cout <<>' false '>;> >return> 0;> }> > // This code is contributed by yashbeersingh42> 

>

>

Java




// Java program to check whether a number> // is prime or not using recursion> import> java.io.*;> > class> GFG {> > >static> int> i =>2>;> > >// Function check whether a number> >// is prime or not> >public> static> boolean> isPrime(>int> n)> >{> > >// Corner cases> >if> (n ==>0> || n ==>1>) {> >return> false>;> >}> > >// Checking Prime> >if> (n == i)> >return> true>;> > >// Base cases> >if> (n % i ==>0>) {> >return> false>;> >}> >i++;> >return> isPrime(n);> >}> > >// Driver Code> >public> static> void> main(String[] args)> >{> >if> (isPrime(>35>)) {> >System.out.println(>'true'>);> >}> >else> {> >System.out.println(>'false'>);> >}> >}> }> > // This code is contributed by divyeshrabadiya07> 

>

>

Python3




# Python3 program to check whether a number> # is prime or not using recursion> > # Function check whether a number> # is prime or not> > > def> isPrime(n, i):> > ># Corner cases> >if> (n>=>=> 0> or> n>=>=> 1>):> >return> False> > ># Checking Prime> >if> (n>=>=> i):> >return> True> > ># Base cases> >if> (n>%> i>=>=> 0>):> >return> False> > >i>+>=> 1> > >return> isPrime(n, i)> > > # Driver Code> if> (isPrime(>35>,>2>)):> >print>(>'true'>)> else>:> >print>(>'false'>)> > # This code is contributed by bunnyram19> 

>

>

C#




// C# program to check whether a number> // is prime or not using recursion> using> System;> class> GFG {> > >static> int> i = 2;> > >// function check whether a number> >// is prime or not> >static> bool> isPrime(>int> n)> >{> > >// corner cases> >if> (n == 0 || n == 1) {> >return> false>;> >}> > >// Checking Prime> >if> (n == i)> >return> true>;> > >// base cases> >if> (n % i == 0) {> >return> false>;> >}> >i++;> >return> isPrime(n);> >}> > >static> void> Main()> >{> >if> (isPrime(35)) {> >Console.WriteLine(>'true'>);> >}> >else> {> >Console.WriteLine(>'false'>);> >}> >}> }> > // This code is contributed by divyesh072019> 

>

>

JavaScript




> >// JavaScript program to check whether a number> >// is prime or not using recursion> > >// function check whether a number> >// is prime or not> >var> i = 2;> > >function> isPrime(n) {> > >// corner cases> >if> (n == 0 || n == 1) {> >return> false>;> >}> > >// Checking Prime> >if> (n == i)>return> true>;> > >// base cases> >if> (n % i == 0) {> >return> false>;> >}> >i++;> >return> isPrime(n);> >}> > >// Driver Code> > >isPrime(35) ? document.write(>' true '>) : document.write(>' false '>);> > >// This code is contributed by rdtank.> >>

montón y clasificación de montón 

>

>

Producción 

 false>

Complejidad del tiempo: EN)
Espacio Auxiliar: O(N) si consideramos la pila de recursividad. De lo contrario, es O(1).

Enfoque eficiente: Una solución eficiente es:

Iterar a través de todos los números de 2 a raíz cuadrada de norte y para cada número verifique si divide a n [porque si un número se expresa como norte = xy y cualquiera de los x o y es mayor que la raíz de n, el otro debe ser menor que el valor de la raíz]. Si encontramos algún número que divida, devolvemos falso.

A continuación se muestra la implementación:

C++14




// A school method based C++ program to> // check if a number is prime> #include> using> namespace> std;> > // Function check whether a number> // is prime or not> bool> isPrime(>int> n)> {> >// Corner case> >if> (n <= 1)> >return> false>;> > >// Check from 2 to square root of n> >for> (>int> i = 2; i <=>sqrt>(n); i++)> >if> (n % i == 0)> >return> false>;> > >return> true>;> }> > // Driver Code> int> main()> {> >isPrime(11) ? cout <<>'true '> : cout <<>'false '>;> >return> 0;> }> 

>

>

Java




// A school method based Java program to> // check if a number is prime> import> java.lang.*;> import> java.util.*;> > class> GFG {> > >// Check for number prime or not> >static> boolean> isPrime(>int> n)> >{> > >// Check if number is less than> >// equal to 1> >if> (n <=>1>)> >return> false>;> > >// Check if number is 2> >else> if> (n ==>2>)> >return> true>;> > >// Check if n is a multiple of 2> >else> if> (n %>2> ==>0>)> >return> false>;> > >// If not, then just check the odds> >for> (>int> i =>3>; i <= Math.sqrt(n); i +=>2>) {> >if> (n % i ==>0>)> >return> false>;> >}> >return> true>;> >}> > >// Driver code> >public> static> void> main(String[] args)> >{> >if> (isPrime(>19>))> >System.out.println(>'true'>);> > >else> >System.out.println(>'false'>);> >}> }> > // This code is contributed by Ronak Bhensdadia> 

>

>

Python3




# A school method based Python3 program> # to check if a number is prime> > > # import sqrt from math module> from> math>import> sqrt> > > > # Function check whether a number> # is prime or not> def> isPrime(n):> > ># Corner case> >if> (n <>=> 1>):> >return> False> > ># Check from 2 to sqrt(n)> >for> i>in> range>(>2>,>int>(sqrt(n))>+>1>):> >if> (n>%> i>=>=> 0>):> >return> False> > >return> True> > > # Driver Code> if> __name__>=>=> '__main__'>:> >if> isPrime(>11>):> >print>(>'true'>)> >else>:> >print>(>'false'>)> > # This code is contributed by Sachin Bisht> 

>

>

C#




// A school method based C# program to> // check if a number is prime> using> System;> > class> GFG {> > >// Function check whether a> >// number is prime or not> >static> bool> isPrime(>int> n)> >{> >// Corner case> >if> (n <= 1)> >return> false>;> > >// Check from 2 to sqrt(n)> >for> (>int> i = 2; i <= Math.Sqrt(n); i++)> >if> (n % i == 0)> >return> false>;> > >return> true>;> >}> > >// Driver Code> >static> void> Main()> >{> >if> (isPrime(11))> >Console.Write(>'true'>);> > >else> >Console.Write(>'false'>);> >}> }> > // This code is contributed by Sam007> 

>

>

JavaScript

lista de matrices en java




// A school method based Javascript program to> // check if a number is prime> > > // Function check whether a number> // is prime or not> function> isPrime(n)> {> >// Corner case> >if> (n <= 1)> >return> false>;> > >// Check from 2 to n-1> >for> (let i = 2; i if (n % i == 0) return false; return true; } // Driver Code isPrime(11) ? console.log(' true') : console.log(' false'); // This code is contributed by Mayank Tyagi> 

>

>

PHP




// A school method based PHP program to // check if a number is prime // Function check whether a number // is prime or not function isPrime($n) { // Corner case if ($n <= 1) return false; // Check from 2 to n-1 for ($i = 2; $i <$n; $i++) if ($n % $i == 0) return false; return true; } // Driver Code if(isPrime(11)) echo('true'); else echo('false'); // This code is contributed by Ajit. ?>> 

>

>

Producción 

true>

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

Otro enfoque eficiente: Para comprobar si el número es primo o no, siga la siguiente idea:

Nos ocuparemos de algunos números como 1, 2, 3 y los números que son divisibles por 2 y 3 en casos separados y para los números restantes. Itere de 5 a sqrt(n) y verifique en cada iteración si (ese valor) o (ese valor + 2) divide n o no e incrementa el valor en 6 [porque cualquier número primo se puede expresar como 6n+1 o 6n-1 ]. Si encontramos algún número que divida, devolvemos falso.

A continuación se muestra la implementación de la idea anterior:

C++




// A school method based C++ program to> // check if a number is prime> #include> using> namespace> std;> > // Function check whether a number> // is prime or not> bool> isPrime(>int> n)> > > // Driver Code> int> main()> {> >isPrime(11) ? cout <<>'true '> : cout <<>'false '>;> >return> 0;> }> // This code is contributed by Suruchi kumari> 

>

>

C




// A school method based C program to> // check if a number is prime> #include> #include> > // Function check whether a number> // is prime or not> int> isPrime(>int> n)> n % 3 == 0)> >return> 0;> >// Check from 5 to square root of n> >// Iterate i by (i+6)> >for> (>int> i = 5; i * i <= n; i = i + 6)> >if> (n % i == 0> > // Driver Code> int> main()> {> >if> (isPrime(11) == 1)> >printf>(>'true '>);> >else> >printf>(>'false '>);> >return> 0;> }> // This code is contributed by Suruchi Kumari> 

>

>

Java




// Java program to check whether a number> import> java.lang.*;> import> java.util.*;> > class> GFG {> > >// Function check whether a number> >// is prime or not> >public> static> boolean> isPrime(>int> n)> >> >if> (n <=>1>)> >return> false>;> > >// Check if n=2 or n=3> >if> (n ==>2> > > >// Driver Code> >public> static> void> main(String[] args)> >{> >if> (isPrime(>11>)) {> >System.out.println(>'true'>);> >}> >else> {> >System.out.println(>'false'>);> >}> >}> }> > // This code is contributed by Sayan Chatterjee> 

>

>

Python3




import> math> > def> is_prime(n:>int>)>->>>bool>:> > ># Check if n=1 or n=0> >if> n <>=> 1>:> >return> 'false'> > ># Check if n=2 or n=3> >if> n>=>=> 2> or> n>=>=> 3>:> >return> 'true'> > ># Check whether n is divisible by 2 or 3> >if> n>%> 2> =>=> 0> or> n>%> 3> =>=> 0>:> >return> 'false'> > ># Check from 5 to square root of n> ># Iterate i by (i+6)> >for> i>in> range>(>5>,>int>(math.sqrt(n))>+>1>,>6>):> >if> n>%> i>=>=> 0> or> n>%> (i>+> 2>)>=>=> 0>:> >return> 'false'> > >return> 'true'> > if> __name__>=>=> '__main__'>:> >print>(is_prime(>11>))> 

>

>

C#




// C# program to check whether a number> using> System;> class> GFG {> > >// Function check whether a number> >// is prime or not> >public> static> bool> isPrime(>int> n)> >> > >// Driver Code> >public> static> void> Main(String[] args)> >{> >if> (isPrime(11)) {> >Console.WriteLine(>'true'>);> >}> >else> {> >Console.WriteLine(>'false'>);> >}> >}> }> > // This code is contributed by Abhijeet> // Kumar(abhijeet_19403)> 

>

>

JavaScript

los primeros mukers




// A school method based JS program to> // check if a number is prime> > > // Function check whether a number> // is prime or not> function> isPrime(n)> n % (i + 2) == 0)> >return> false>;> > >return> true>;> > > // Driver Code> isPrime(11) ? console.log(>'true'>) : console.log(>'false'>);> > > // This code is contributed by phasing17> 

>

>

Producción 

true>

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

Soluciones eficientes

  • Prueba de primalidad | Conjunto 1 (Introducción y Método Escolar)
  • Prueba de primalidad | Conjunto 2 (Método Fermat)
  • Prueba de primalidad | Conjunto 3 (Miller-Rabin)
  • Prueba de primalidad | Serie 4 (Solovay-Strassen)
  • Prueba de primalidad de Lucas

Algoritmos para encontrar todos los números primos menores que N.

  • Tamiz de Eratóstenes
  • Tamiz de Eratóstenes en complejidad temporal 0(n)
  • Tamiz segmentado
  • Tamiz de Sundaram
  • Tamiz bit a bit
  • Artículos recientes sobre Sieve!

Más problemas relacionados con el número primo

  • Encuentra dos números primos distintos con a producto dado
  • Imprime todos los números primos menores o iguales a N
  • Programa recursivo para números primos.
  • Encuentra dos números primos con a suma dada
  • Encuentre el dígito más alto en números primos en un rango
  • Factorización prima usando Sieve O (log n) para múltiples consultas
  • Programa para imprimir todos los factores primos de un número dado
  • Factor mínimo primo de números hasta n
  • Factores primos del MCM de elementos de una matriz – techcodeview.com
  • Programa para la conjetura de Goldbach
  • Números primos y Fibonacci
  • Número compuesto
  • ¡Artículos recientes sobre números primos!