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>
Producción:
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