Un número compuesto es un entero positivo que no es primo . En otras palabras, tiene un divisor positivo distinto de uno o de sí mismo. Los primeros números compuestos son 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, ………
- Todo entero mayor que uno es un número primo o un número compuesto.
- El número uno es una unidad, no es ni primo ni compuesto.
¿Cómo verificar si un número dado es un número compuesto o no?
Ejemplos:
Input : n = 21 Output: Yes The number is a composite number! Input : n = 11 Output : No
La idea es simple, podemos usar cualquiera de los siguientes métodos para la verificación principal. Solo necesitamos cambiar las declaraciones de devolución. Devolver verdadero se cambia para devolver falso y viceversa.
- Prueba de primalidad | Conjunto 1 (Introducción y Método Escolar)
- Prueba de primalidad | Juego 2 (Método Fermat)
- Prueba de primalidad | Conjunto 3 (Miller-Rabin)
En el siguiente código se analiza el método de escuela optimizado.
C++
// A optimized school method based C++ program to check // if a number is composite. #include <bits/stdc++.h> using namespace std; bool isComposite(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return false; // This is checked so that we can skip // middle five numbers in below loop if (n%2 == 0 || n%3 == 0) return true; for (int i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0) return true; return false; } // Driver Program to test above function int main() { isComposite(11)? cout << " true\n": cout << " false\n"; isComposite(15)? cout << " true\n": cout << " false\n"; return 0; }
Java
/// An optimized method based Java // program to check if a number // is Composite or not. import java.io.*; class Composite { static boolean isComposite(int n) { // Corner cases if (n <= 1) System.out.println("False"); if (n <= 3) System.out.println("False"); // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return true; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false; } // Driver Program to test above function public static void main(String args[]) { System.out.println(isComposite(11) ? "true" : "false"); System.out.println(isComposite(15) ? "true" : "false"); } } // This code is contributed by Anshika Goyal
Python 3
# A optimized school method based Python program to check # if a number is composite. def isComposite(n): # Corner cases if (n <= 1): return False if (n <= 3): return False # This is checked so that we can skip # middle five numbers in below loop if (n % 2 == 0 or n % 3 == 0): return True i = 5 while(i * i <= n): if (n % i == 0 or n % (i + 2) == 0): return True i = i + 6 return False # Driver Program to test above function print("true") if(isComposite(11)) else print("false") print("true") if(isComposite(15)) else print("false") # This code is contributed by Anant Agarwal.
C#
// A optimized school method based C# program // to check if a number is composite. using System; namespace Composite { public class GFG { public static bool isComposite(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return false; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return true; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false; } // Driver Code public static void Main() { if(isComposite(11)) Console.WriteLine("true"); else Console.WriteLine("false"); if(isComposite(15)) Console.WriteLine("true"); else Console.WriteLine("false"); } } } // This code is contributed by Sam007
PHP
<?php // A optimized school // method based PHP // program to check // if a number is composite. function isComposite($n) { // Corner cases if ($n <= 1) return false; if ($n <= 3) return false; // This is checked so // that we can skip // middle five numbers // in below loop if ($n%2 == 0 || $n % 3 == 0) return true; for ($i = 5; $i * $i <= $n; $i = $i + 6) if ($n % $i == 0 || $n % ($i + 2) == 0) return true; return false; } // Driver Code if(isComposite(11)) echo "true"; else echo "false"; echo"\n"; if(isComposite(15)) echo "true"; else echo "false"; echo"\n"; // This code is contributed by Ajit. ?>
Javascript
<script> // A optimized school method based Javascript program to check // if a number is composite. function isComposite(n) { // Corner cases if (n <= 1) return false; if (n <= 3) return false; // This is checked so that we can skip // middle five numbers in below loop if (n%2 == 0 || n%3 == 0) return true; for (let i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0) return true; return false; } // Driver Program to test above function isComposite(11)? document.write(" true" + "<br>"): document.write(" false" + "<br>"); isComposite(15)? document.write(" true" + "<br>"): document.write(" false" + "<br>"); // This code is contributed by Mayank Tyagi </script>
Producción:
false true
Complejidad de tiempo: – O (sqrt (n))
Complejidad Espacial:-O(1)
Programa sobre Números Compuestos
- Encuentra un rango de números compuestos de longitud dada
- Generar una lista de n números compuestos consecutivos (Un método interesante)
- Suma y producto de k números compuestos más pequeños y k más grandes en la array
- Producto de todos los Números Compuestos en una array
- Recuento y suma de elementos compuestos en una array
- Dividir n en números compuestos máximos
Referencia:
https://en.wikipedia.org/wiki/Composite_number
Este artículo es una contribución de Ajay Puri . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA