Dado un número N , la tarea es encontrar el número que es menor o igual a N cuyo producto de factores primos es máximo.
Nota: Si hay más de un número cuyo producto máximo es igual, imprima el número más pequeño de ellos.
Ejemplos:
Entrada: N = 12
Salida: 11
Explicación:
Producto del factor primo de todos los números anteriores a N:
2 = 2
3 = 3
4 = 2
5 = 5
6 = 2 * 3 = 6
7 = 7
8 = 2
9 = 3
10 = 2 * 5 = 10
11 = 11
12 = 2*3 = 6
El máximo de todos los anteriores es 11.
Entrada: N = 20
Salida: 19
Planteamiento: La idea es usar el concepto de Criba de Eratóstenes para encontrar el producto de todos los factores primos de N números y luego encontrar el número mínimo cuyo producto de factores primos sea máximo. A continuación se muestran los pasos:
- Cree una lista de números del 1 al N e inicialice cada valor con 1.
- Sea p = 2 que es el primer número primo. Iterar desde p , contar en incrementos de p y multiplicar por p en cada índice de la lista. Estos índices serán p(p+1), p(p+2), p(p+3), etc.
Por ejemplo:
If p is a prime number, then multiply with p at every index which is multiple of p. For p = 2, Multiply with 2 at index 2, 4, 6, 8, 10,..., till N.
- Repita el paso anterior para todos los números primos hasta N.
- Después de encontrar el producto de todos los factores primos hasta N , recorre la lista de números y encuentra el menor número con el máximo producto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest number
// having a maximum product of prime factors
int maxPrimefactorNum(int N)
{
// Declare the array arr[]
int arr[N + 1];
// Initialise array with 1
for (int i = 0; i < N + 1; i++)
arr[i] = 1;
// Iterate from [2, N]
for (int i = 2; i <= N; i++) {
// If value at index i is 1,
// then i is prime and make
// update array at index for
// all multiples of i
if (arr[i] == 1) {
for (int j = i; j <= N; j += i) {
arr[j] *= i;
}
}
}
// Initialise maxValue
int maxValue = 1;
// Find number having maximum product
// of prime factor <= N
for (int i = 2; i <= N; i++) {
if (arr[i] > maxValue) {
maxValue = i;
}
}
// Find the maximum value
return maxValue;
}
// Driven Code
int main()
{
// Given Number
int N = 20;
// Function call
cout << maxPrimefactorNum(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the smallest number
// having a maximum product of prime factors
static int maxPrimefactorNum(int N)
{
// Declare the array arr[]
int []arr = new int[N + 1];
// Initialise array with 1
for(int i = 0; i < N + 1; i++)
arr[i] = 1;
// Iterate from [2, N]
for(int i = 2; i <= N; i++)
{
// If value at index i is 1,
// then i is prime and make
// update array at index for
// all multiples of i
if (arr[i] == 1)
{
for(int j = i; j <= N; j += i)
{
arr[j] *= i;
}
}
}
// Initialise maxValue
int maxValue = 1;
// Find number having maximum product
// of prime factor <= N
for(int i = 2; i<= N; i++)
{
if (arr[i] > maxValue)
{
maxValue = i;
}
}
// Find the maximum value
return maxValue;
}
// Driver Code
public static void main(String[] args)
{
// Given number
int N = 20;
// Function call
System.out.print(maxPrimefactorNum(N));
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program for the above approach # Function to find the smallest number # having a maximum product of prime factors def maxPrimefactorNum(N): # Declare the list arr arr = [] # Initialise list with 1 for i in range(N + 1): arr.append(1) # Iterate from [2, N] for i in range(2, N + 1): # If value at index i is 1, # then i is prime and make # update list at index for # all multiples of i if (arr[i] == 1) : for j in range(i, N + 1, i): arr[j] *= i # Initialise maxValue maxValue = 1 # Find number having maximum product # of prime factor <= N for i in range(2, N + 1): if (arr[i] > maxValue): maxValue = i # Find the maximum value return maxValue # Driver Code # Given number N = 20; # Function call print(maxPrimefactorNum(N)) # This code is contributed by yatinagg
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the smallest number
// having a maximum product of prime factors
static int maxPrimefactorNum(int N)
{
// Declare the array []arr
int []arr = new int[N + 1];
// Initialise array with 1
for(int i = 0; i < N + 1; i++)
arr[i] = 1;
// Iterate from [2, N]
for(int i = 2; i <= N; i++)
{
// If value at index i is 1,
// then i is prime and make
// update array at index for
// all multiples of i
if (arr[i] == 1)
{
for(int j = i; j <= N; j += i)
{
arr[j] *= i;
}
}
}
// Initialise maxValue
int maxValue = 1;
// Find number having maximum product
// of prime factor <= N
for(int i = 2; i<= N; i++)
{
if (arr[i] > maxValue)
{
maxValue = i;
}
}
// Find the maximum value
return maxValue;
}
// Driver Code
public static void Main(String[] args)
{
// Given number
int N = 20;
// Function call
Console.Write(maxPrimefactorNum(N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program for the above approach
// Function to find the smallest number
// having a maximum product of prime factors
function maxPrimefactorNum( N)
{
// Declare the array arr[]
let arr=Array(N + 1).fill(1);
// Initialise array with 1
//for (int i = 0; i < N + 1; i++)
// arr[i] = 1;
// Iterate from [2, N]
for (let i = 2; i <= N; i++) {
// If value at index i is 1,
// then i is prime and make
// update array at index for
// all multiples of i
if (arr[i] == 1) {
for (let j = i; j <= N; j += i) {
arr[j] *= i;
}
}
}
// Initialise maxValue
let maxValue = 1;
// Find number having maximum product
// of prime factor <= N
for (let i = 2; i <= N; i++) {
if (arr[i] > maxValue) {
maxValue = i;
}
}
// Find the maximum value
return maxValue;
}
// Driven Code
// Given Number
let N = 20;
// Function call
document.write(maxPrimefactorNum(N));
// This code contributed by Rajput-Ji
</script>
Producción:
19
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)