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