Dado un número entero N , la tarea es encontrar la suma de los exponentes de los factores primos de los números 1 a N.
Ejemplos:
Entrada: N = 4
Salida: 4
Explicación:
Los números hasta 4 son 1, 2, 3, 4 donde
El exponente de 1 en la factorización prima de 1 es 0 (2 0 ),
Para 2 es 1 (2 1 ),
Para 3 es 1 (3 1 ), y
Para 4 es 2 (2 2 ).
La suma del exponente de los factores primos de cada número hasta 4 es 0 + 1 + 1 + 2 = 4.Entrada: N = 10
Salida: 15
Explicación:
la suma del exponente de los factores primos de cada número hasta 10 es 15.
Planteamiento: La idea es utilizar el concepto de Factores primos y sus potencias. A continuación se muestran los pasos:
- Iterar para cada número de 2 a N y para cada número hacer lo siguiente:
- encuentra la potencia de los factores primos para cada número N .
- Encuentra la suma de cada potencia en los pasos anteriores
- Imprime la suma de todas las potencias de los factores primos de N e imprime la suma.
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 implement sieve of
// eratosthenes
void sieveOfEratosthenes(int N, int s[])
{
// Create a boolean array and
// initialize all entries as false
vector<bool> prime(N + 1, false);
// Initializing smallest
// factor equal to 2
// for all the even numbers
for (int i = 2; i <= N; i += 2)
s[i] = 2;
// Iterate for odd numbers
// less then equal to n
for (int i = 3; i <= N; i += 2) {
if (prime[i] == false) {
// s(i) for a prime is
// the number itself
s[i] = i;
// For all multiples of
// current prime number
for (int j = i;
j * i <= N; j += 2) {
if (prime[i * j] == false) {
prime[i * j] = true;
// i is the smallest
// prime factor for
// number "i*j"
s[i * j] = i;
}
}
}
}
}
// Function to generate prime
// factors and its power
int generatePrimeFactors(int N)
{
// s[i] is going to store
// smallest prime factor of i
int s[N + 1];
int sum = 0;
sieveOfEratosthenes(N, s);
// Current prime factor of N
int curr = s[N];
// Power of current prime factor
int cnt = 1;
// Calculating prime factors
// and their powers sum
while (N > 1) {
N /= s[N];
if (curr == s[N]) {
// Increment the count and
// continue the process
cnt++;
continue;
}
// Add count to the sum
sum = sum + cnt;
curr = s[N];
// Reinitialize count
cnt = 1;
}
// Return the result
return sum;
}
// Function to find the sum of all the
// power of prime factors of N
void findSum(int N)
{
int sum = 0;
// Iterate for in [2, N]
for (int i = 2; i <= N; i++) {
sum += generatePrimeFactors(i);
}
cout << sum << endl;
}
// Driver Code
int main()
{
// Given Number N
int N = 4;
// Function Call
findSum(N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to implement sieve of
// eratosthenes
static void sieveOfEratosthenes(int N, int s[])
{
// Create a boolean array and
// initialize all entries as false
boolean []prime = new boolean[N + 1];
// Initializing smallest
// factor equal to 2
// for all the even numbers
for(int i = 2; i <= N; i += 2)
s[i] = 2;
// Iterate for odd numbers
// less then equal to n
for(int i = 3; i <= N; i += 2)
{
if (prime[i] == false)
{
// s(i) for a prime is
// the number itself
s[i] = i;
// For all multiples of
// current prime number
for(int j = i;
j * i <= N; j += 2)
{
if (prime[i * j] == false)
{
prime[i * j] = true;
// i is the smallest
// prime factor for
// number "i*j"
s[i * j] = i;
}
}
}
}
}
// Function to generate prime
// factors and its power
static int generatePrimeFactors(int N)
{
// s[i] is going to store
// smallest prime factor of i
int []s = new int[N + 1];
int sum = 0;
sieveOfEratosthenes(N, s);
// Current prime factor of N
int curr = s[N];
// Power of current prime factor
int cnt = 1;
// Calculating prime factors
// and their powers sum
while (N > 1)
{
N /= s[N];
if (curr == s[N])
{
// Increment the count and
// continue the process
cnt++;
continue;
}
// Add count to the sum
sum = sum + cnt;
curr = s[N];
// Reinitialize count
cnt = 1;
}
// Return the result
return sum;
}
// Function to find the sum of all the
// power of prime factors of N
static void findSum(int N)
{
int sum = 0;
// Iterate for in [2, N]
for(int i = 2; i <= N; i++)
{
sum += generatePrimeFactors(i);
}
System.out.print(sum + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given Number N
int N = 4;
// Function Call
findSum(N);
}
}
// This code is contributed by Ajay Kumar
Python3
# Python3 program for the above approach # Function to implement sieve of # eratosthenes def sieveOfEratosthenes(N, s): # Create a boolean array and # initialize all entries as false prime = [False] * (N + 1) # Initializing smallest # factor equal to 2 # for all the even numbers for i in range(2, N + 1, 2): s[i] = 2 # Iterate for odd numbers # less then equal to n for i in range(3, N + 1, 2): if (prime[i] == False): # s(i) for a prime is # the number itself s[i] = i # For all multiples of # current prime number j = i while (j * i <= N): if (prime[i * j] == False): prime[i * j] = True # i is the smallest # prime factor for # number "i*j" s[i * j] = i j += 2 # Function to generate prime # factors and its power def generatePrimeFactors(N): # s[i] is going to store # smallest prime factor of i s = [0] * (N + 1) sum = 0 sieveOfEratosthenes(N, s) # Current prime factor of N curr = s[N] # Power of current prime factor cnt = 1 # Calculating prime factors # and their powers sum while (N > 1): N //= s[N] if (curr == s[N]): # Increment the count and # continue the process cnt += 1 continue # Add count to the sum sum = sum + cnt curr = s[N] # Reinitialize count cnt = 1 # Return the result return sum # Function to find the sum of all the # power of prime factors of N def findSum (N): sum = 0 # Iterate for in [2, N] for i in range(2, N + 1): sum += generatePrimeFactors(i) print(sum) # Driver Code if __name__ == '__main__': # Given number N N = 4 # Function call findSum(N) # This code is contributed by himanshu77
C#
// C# program for the above approach
using System;
class GFG{
// Function to implement sieve of
// eratosthenes
static void sieveOfEratosthenes(int N, int []s)
{
// Create a bool array and
// initialize all entries as false
bool []prime = new bool[N + 1];
// Initializing smallest
// factor equal to 2
// for all the even numbers
for(int i = 2; i <= N; i += 2)
s[i] = 2;
// Iterate for odd numbers
// less then equal to n
for(int i = 3; i <= N; i += 2)
{
if (prime[i] == false)
{
// s(i) for a prime is
// the number itself
s[i] = i;
// For all multiples of
// current prime number
for(int j = i;
j * i <= N; j += 2)
{
if (prime[i * j] == false)
{
prime[i * j] = true;
// i is the smallest
// prime factor for
// number "i*j"
s[i * j] = i;
}
}
}
}
}
// Function to generate prime
// factors and its power
static int generatePrimeFactors(int N)
{
// s[i] is going to store
// smallest prime factor of i
int []s = new int[N + 1];
int sum = 0;
sieveOfEratosthenes(N, s);
// Current prime factor of N
int curr = s[N];
// Power of current prime factor
int cnt = 1;
// Calculating prime factors
// and their powers sum
while (N > 1)
{
N /= s[N];
if (curr == s[N])
{
// Increment the count and
// continue the process
cnt++;
continue;
}
// Add count to the sum
sum = sum + cnt;
curr = s[N];
// Reinitialize count
cnt = 1;
}
// Return the result
return sum;
}
// Function to find the sum of all the
// power of prime factors of N
static void findSum(int N)
{
int sum = 0;
// Iterate for in [2, N]
for(int i = 2; i <= N; i++)
{
sum += generatePrimeFactors(i);
}
Console.Write(sum + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given number N
int N = 4;
// Function call
findSum(N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to implement sieve of
// eratosthenes
function sieveOfEratosthenes(N, s)
{
// Create a boolean array and
// initialize all entries as false
let prime = Array.from({length: N+1}, (_, i) => 0);
// Initializing smallest
// factor equal to 2
// for all the even numbers
for(let i = 2; i <= N; i += 2)
s[i] = 2;
// Iterate for odd numbers
// less then equal to n
for(let i = 3; i <= N; i += 2)
{
if (prime[i] == false)
{
// s(i) for a prime is
// the number itself
s[i] = i;
// For all multiples of
// current prime number
for(let j = i;
j * i <= N; j += 2)
{
if (prime[i * j] == false)
{
prime[i * j] = true;
// i is the smallest
// prime factor for
// number "i*j"
s[i * j] = i;
}
}
}
}
}
// Function to generate prime
// factors and its power
function generatePrimeFactors(N)
{
// s[i] is going to store
// smallest prime factor of i
let s = Array.from({length: N+1}, (_, i) => 0);
let sum = 0;
sieveOfEratosthenes(N, s);
// Current prime factor of N
let curr = s[N];
// Power of current prime factor
let cnt = 1;
// Calculating prime factors
// and their powers sum
while (N > 1)
{
N /= s[N];
if (curr == s[N])
{
// Increment the count and
// continue the process
cnt++;
continue;
}
// Add count to the sum
sum = sum + cnt;
curr = s[N];
// Reinitialize count
cnt = 1;
}
// Return the result
return sum;
}
// Function to find the sum of all the
// power of prime factors of N
function findSum(N)
{
let sum = 0;
// Iterate for in [2, N]
for(let i = 2; i <= N; i++)
{
sum += generatePrimeFactors(i);
}
document.write(sum + "\n");
}
// Driver Code
// Given Number N
let N = 4;
// Function Call
findSum(N);
</script>
Producción:
4
Complejidad de tiempo: O(N*log 2 N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Akashkumar17 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA