Dado un número compuesto N , la tarea es encontrar el número compuesto más grande que divide a N y es estrictamente menor que N. Si no existe tal número, imprima -1.
Ejemplos:
Entrada: N = 16
Salida: 8
Explicación:
Todos los números que dividen a 16 son { 1, 2, 4, 8, 16 }
de los cuales 8 es el número compuesto más grande (menor que 16) que divide a 16.
Entrada: N = 100
Salida : -1
Enfoque:
dado que N es un número compuesto, N puede ser el producto de dos números, de modo que uno sea un número primo y otro sea un número compuesto y, si no podemos encontrar ese par para N , entonces el número compuesto más grande que es menor que N que divide a N no existe.
Para encontrar el número compuesto más grande, encuentre el número primo más pequeño ( digamos a) que divide a N. Entonces el mayor número compuesto que divide a N y menor que N puede estar dado por (N/a) .
Los siguientes son los pasos:
- Encuentre el número primo más pequeño de N (digamos a).
- Compruebe si (N/a) es primo o no. Si es así, entonces no podemos encontrar el número compuesto más grande.
- Else (N/a) es el mayor número compuesto que divide a N y es menor que N .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the largest // composite number that divides // N which is less than N #include <bits/stdc++.h> using namespace std; // Function to check whether // a number is prime or not bool isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to n-1 for (int i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Function that find the largest // composite number which divides // N and less than N int getSmallestPrimefactor(int n) { // Find the prime number for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return i; } } // Driver's Code int main() { int N = 100; int a; // Get the smallest prime // factor a = getSmallestPrimefactor(N); // Check if (N/a) is prime // or not // If Yes print "-1" if (isPrime(N / a)) { cout << "-1"; } // Else print largest composite // number (N/a) else { cout << N / a; } return 0; }
Java
// Java program to find the largest // composite number that divides // N which is less than N import java.util.*; class GFG{ // Function to check whether // a number is prime or not static boolean isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to n-1 for(int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; } // Function that find the largest // composite number which divides // N and less than N static int getSmallestPrimefactor(int n) { // Find the prime number for(int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return i; } return -1; } // Driver Code public static void main(String[] args) { int N = 100; int a; // Get the smallest prime // factor a = getSmallestPrimefactor(N); // Check if (N/a) is prime or // not. If Yes print "-1" if (isPrime(N / a)) { System.out.print("-1"); } // Else print largest composite // number (N/a) else { System.out.print(N / a); } } } // This code is contributed by amal kumar choubey
Python3
# Python3 program to find the largest # composite number that divides # N which is less than N import math # Function to check whether # a number is prime or not def isPrime(n): # Corner case if (n <= 1): return False; # Check from 2 to n-1 for i in range(2, n): if (n % i == 0): return False; return True; # Function that find the largest # composite number which divides # N and less than N def getSmallestPrimefactor(n): # Find the prime number for i in range(2, (int)(math.sqrt(n) + 1)): if (n % i == 0): return i; return -1 # Driver Code N = 100; # Get the smallest prime # factor a = getSmallestPrimefactor(N); # Check if (N/a) is prime # or not. If Yes print "-1" if ((isPrime((int)(N / a)))): print(-1) # Else print largest composite # number (N/a) else: print((int)(N / a)); # This code is contributed by grand_master
C#
// C# program to find the largest // composite number that divides // N which is less than N using System; class GFG{ // Function to check whether // a number is prime or not static bool isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to n-1 for(int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; } // Function that find the largest // composite number which divides // N and less than N static int getSmallestPrimefactor(int n) { // Find the prime number for(int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) return i; } return -1; } // Driver Code public static void Main() { int N = 100; int a; // Get the smallest prime // factor a = getSmallestPrimefactor(N); // Check if (N/a) is prime or // not. If Yes print "-1" if (isPrime(N / a)) { Console.Write("-1"); } // Else print largest composite // number (N/a) else { Console.Write(N / a); } } } // This code is contributed by Code_Mech
Javascript
<script> // Javascript program to find the largest // composite number that divides // N which is less than N // Function to check whether // a number is prime or not function isPrime(n) { // Corner case if (n <= 1) return false; var i; // Check from 2 to n-1 for (i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Function that find the largest // composite number which divides // N and less than N function getSmallestPrimefactor(n) { var i; // Find the prime number for (i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return i; } } // Driver's Code var N = 100; var a; // Get the smallest prime // factor a = getSmallestPrimefactor(N); // Check if (N/a) is prime // or not // If Yes print "-1" if (isPrime(N / a)) document.write("-1"); // Else print largest composite // number (N/a) else document.write(N/a); </script>
50
Complejidad del tiempo: O(sqrt(N))
Publicación traducida automáticamente
Artículo escrito por shshankchugh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA