Dada una array arr[] , la tarea es encontrar la suma del factor primo máximo y mínimo de cada número en la array dada. Ejemplos:
Entrada: arr[] = {15}
Salida: 8
Los factores primos máximo y mínimo
de 15 son 5 y 3 respectivamente.
Entrada: arr[] = {5, 10, 15, 20, 25, 30}
Salida: 10 7 8 7 10 7
Enfoque: la idea es usar la criba de Eratóstenes para precalcular todos los factores primos mínimos y máximos de cada número y almacenarlos en dos arrays. Después de este cálculo previo, la suma del factor primo mínimo y máximo se puede encontrar en tiempo constante.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100000;
// max_prime[i] represent maximum prime
// number that divides the number i
int max_prime[MAX];
// min_prime[i] represent minimum prime
// number that divides the number i
int min_prime[MAX];
// Function to store the minimum prime factor
// and the maximum prime factor in two arrays
void sieve(int n)
{
for (int i = 2; i <= n; ++i) {
// Check for prime number
// if min_prime[i]>0,
// then it is not a prime number
if (min_prime[i] > 0) {
continue;
}
// if i is a prime number
// min_prime number that divide prime number
// and max_prime number that divide prime number
// is the number itself.
min_prime[i] = i;
max_prime[i] = i;
int j = i + i;
while (j <= n) {
if (min_prime[j] == 0) {
// If this number is being visited
// for first time then this divisor
// must be the smallest prime number
// that divides this number
min_prime[j] = i;
}
// Update prime number till
// last prime number that divides this number
// The last prime number that
// divides this number will be maximum.
max_prime[j] = i;
j += i;
}
}
}
// Function to find the sum of the minimum
// and the maximum prime factors of every
// number from the given array
void findSum(int arr[], int n)
{
// Pre-calculation
sieve(MAX);
// For every element of the given array
for (int i = 0; i < n; i++) {
// The sum of its smallest
// and largest prime factor
int sum = min_prime[arr[i]]
+ max_prime[arr[i]];
cout << sum << " ";
}
}
// Driver code
int main()
{
int arr[] = { 5, 10, 15, 20, 25, 30 };
int n = sizeof(arr) / sizeof(int);
findSum(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int MAX = 100000;
// max_prime[i] represent maximum prime
// number that divides the number i
static int max_prime[] = new int[MAX + 1];
// min_prime[i] represent minimum prime
// number that divides the number i
static int min_prime[] = new int[MAX + 1];
// Function to store the minimum prime factor
// and the maximum prime factor in two arrays
static void sieve(int n)
{
for (int i = 2; i <= n; ++i)
{
// Check for prime number
// if min_prime[i] > 0,
// then it is not a prime number
if (min_prime[i] > 0)
{
continue;
}
// if i is a prime number
// min_prime number that divide prime number
// and max_prime number that divide prime number
// is the number itself.
min_prime[i] = i;
max_prime[i] = i;
int j = i + i;
while (j <= n)
{
if (min_prime[j] == 0)
{
// If this number is being visited
// for first time then this divisor
// must be the smallest prime number
// that divides this number
min_prime[j] = i;
}
// Update prime number till
// last prime number that divides this number
// The last prime number that
// divides this number will be maximum.
max_prime[j] = i;
j += i;
}
}
}
// Function to find the sum of the minimum
// and the maximum prime factors of every
// number from the given array
static void findSum(int arr[], int n)
{
// Pre-calculation
sieve(MAX);
// For every element of the given array
for (int i = 0; i < n; i++)
{
// The sum of its smallest
// and largest prime factor
int sum = min_prime[arr[i]]
+ max_prime[arr[i]];
System.out.print(sum + " ");
}
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 5, 10, 15, 20, 25, 30 };
int n = arr.length ;
findSum(arr, n);
}
}
// This code is contributed by AnkitRai01
Python
# Python3 implementation of the approach MAX = 100000 # max_prime[i] represent maximum prime # number that divides the number i max_prime = [0]*(MAX + 1) # min_prime[i] represent minimum prime # number that divides the number i min_prime = [0]*(MAX + 1) # Function to store the minimum prime factor # and the maximum prime factor in two arrays def sieve(n): for i in range(2, n + 1): # Check for prime number # if min_prime[i]>0, # then it is not a prime number if (min_prime[i] > 0): continue # if i is a prime number # min_prime number that divide prime number # and max_prime number that divide prime number # is the number itself. min_prime[i] = i max_prime[i] = i j = i + i while (j <= n): if (min_prime[j] == 0): # If this number is being visited # for first time then this divisor # must be the smallest prime number # that divides this number min_prime[j] = i # Update prime number till # last prime number that divides this number # The last prime number that # divides this number will be maximum. max_prime[j] = i j += i # Function to find the sum of the minimum # and the maximum prime factors of every # number from the given array def findSum(arr, n): # Pre-calculation sieve(MAX) # For every element of the given array for i in range(n): # The sum of its smallest # and largest prime factor sum = min_prime[arr[i]] + max_prime[arr[i]] print(sum, end = " ") # Driver code arr = [5, 10, 15, 20, 25, 30] n = len(arr) findSum(arr, n) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 100000;
// max_prime[i] represent maximum prime
// number that divides the number i
static int []max_prime = new int[MAX + 1];
// min_prime[i] represent minimum prime
// number that divides the number i
static int []min_prime = new int[MAX + 1];
// Function to store the minimum prime factor
// and the maximum prime factor in two arrays
static void sieve(int n)
{
for (int i = 2; i <= n; ++i)
{
// Check for prime number
// if min_prime[i] > 0,
// then it is not a prime number
if (min_prime[i] > 0)
{
continue;
}
// if i is a prime number
// min_prime number that divide prime number
// and max_prime number that divide prime number
// is the number itself.
min_prime[i] = i;
max_prime[i] = i;
int j = i + i;
while (j <= n)
{
if (min_prime[j] == 0)
{
// If this number is being visited
// for first time then this divisor
// must be the smallest prime number
// that divides this number
min_prime[j] = i;
}
// Update prime number till
// last prime number that divides this number
// The last prime number that
// divides this number will be maximum.
max_prime[j] = i;
j += i;
}
}
}
// Function to find the sum of the minimum
// and the maximum prime factors of every
// number from the given array
static void findSum(int []arr, int n)
{
// Pre-calculation
sieve(MAX);
// For every element of the given array
for (int i = 0; i < n; i++)
{
// The sum of its smallest
// and largest prime factor
int sum = min_prime[arr[i]]
+ max_prime[arr[i]];
Console.Write(sum + " ");
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 5, 10, 15, 20, 25, 30 };
int n = arr.Length ;
findSum(arr, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
var MAX = 100000;
// max_prime[i] represent maximum prime
// number that divides the number i
var max_prime = Array.from({length: MAX + 1}, (_, i) => 0);
// min_prime[i] represent minimum prime
// number that divides the number i
var min_prime = Array.from({length: MAX + 1}, (_, i) => 0);
// Function to store the minimum prime factor
// and the maximum prime factor in two arrays
function sieve(n)
{
for (var i = 2; i <= n; ++i)
{
// Check for prime number
// if min_prime[i] > 0,
// then it is not a prime number
if (min_prime[i] > 0)
{
continue;
}
// if i is a prime number
// min_prime number that divide prime number
// and max_prime number that divide prime number
// is the number itself.
min_prime[i] = i;
max_prime[i] = i;
var j = i + i;
while (j <= n)
{
if (min_prime[j] == 0)
{
// If this number is being visited
// for first time then this divisor
// must be the smallest prime number
// that divides this number
min_prime[j] = i;
}
// Update prime number till
// last prime number that divides this number
// The last prime number that
// divides this number will be maximum.
max_prime[j] = i;
j += i;
}
}
}
// Function to find the sum of the minimum
// and the maximum prime factors of every
// number from the given array
function findSum(arr , n)
{
// Pre-calculation
sieve(MAX);
// For every element of the given array
for (i = 0; i < n; i++)
{
// The sum of its smallest
// and largest prime factor
var sum = min_prime[arr[i]]
+ max_prime[arr[i]];
document.write(sum + " ");
}
}
// Driver code
var arr = [ 5, 10, 15, 20, 25, 30 ];
var n = arr.length ;
findSum(arr, n);
// This code contributed by shikhasingrajput
</script>
Producción:
10 7 8 7 10 7
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(100000)
Publicación traducida automáticamente
Artículo escrito por shivamsinghal1012 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA