Dados dos enteros L y R. La tarea es encontrar la suma de todos los factores primos de cada número en el rango [LR].
Ejemplos:
Entrada: l = 5, r = 10
Salida: 17
5 es primo, por lo tanto suma de factores = 0
6 tiene factores primos 2 y 3, por lo tanto suma = 5
7 es primo, por lo tanto suma = 0
8 tiene factor primo 2, por lo tanto suma = 2
9 tiene factor primo 3, por lo tanto suma = 3
10 tiene factores primos 2 y 5, por lo tanto suma = 7
Por lo tanto, suma total = 5 + 2 + 3 + 7 = 17
Entrada: l = 18, r = 25
Salida: 45
18 tiene factores primos 2, 3 por lo tanto suma = 5
19 es primo, por lo tanto suma de factores = 0
20 tiene factores primos 2 y 5, por lo tanto suma = 7
21 tiene factores primos 3 y 7, por lo tanto suma = 10
22 tiene factores primos 2 y 11, por lo tanto sum = 13
23 es primo. por lo tanto suma = 0
24 tiene factores primos 2 y 3, por lo tanto suma = 5
25 tiene factor primo 5, por lo tanto suma = 5
Por lo tanto, suma total = 5 + 7 + 10 + 13 + 5 + 5 = 45
Un enfoque ingenuo sería comenzar a iterar a través de todos los números de l a r. Para cada iteración, comience desde 2 hasta i y encuentre si i es divisible por ese número, si es divisible, simplemente sumamos i y procedemos.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the sum of prime
// factors of all numbers in range [L-R]
#include <iostream>
using namespace std;
bool isPrime(int n)
{
for (int i = 2; i * i <= n; i++) {
// n has a factor, hence not a prime
if (n % i == 0)
return false;
}
// we reach here if n has no factors
// and hence n is a prime number
return true;
}
int sum(int l, int r)
{
int sum = 0;
// iterate from lower to upper
for (int i = l; i <= r; i++) {
// if i is prime, it has no factors
if (isPrime(i))
continue;
for (int j = 2; j < i; j++) {
// check if j is a prime factor of i
if (i % j == 0 && isPrime(j))
sum += j;
}
}
return sum;
}
// Driver code
int main() {
int l = 18, r = 25;
cout<<(sum(l, r));
return 0;
}
Java
// Java program to find the sum of prime
// factors of all numbers in range [L-R]
class gfg {
static boolean isPrime(int n)
{
for (int i = 2; i * i <= n; i++) {
// n has a factor, hence not a prime
if (n % i == 0)
return false;
}
// we reach here if n has no factors
// and hence n is a prime number
return true;
}
static int sum(int l, int r)
{
int sum = 0;
// iterate from lower to upper
for (int i = l; i <= r; i++) {
// if i is prime, it has no factors
if (isPrime(i))
continue;
for (int j = 2; j < i; j++) {
// check if j is a prime factor of i
if (i % j == 0 && isPrime(j))
sum += j;
}
}
return sum;
}
// Driver code
public static void main(String[] args)
{
int l = 18, r = 25;
System.out.println(sum(l, r));
}
}
Python3
# Python3 program to find the sum of prime # factors of all numbers in range [L-R] def isPrime(n): i = 2 while i * i <= n: # n has a factor, hence not a prime if (n % i == 0): return False i += 1 # we reach here if n has no factors # and hence n is a prime number return True def sum(l, r): sum = 0 # iterate from lower to upper for i in range(l, r + 1) : # if i is prime, it has no factors if (isPrime(i)) : continue for j in range(2, i): # check if j is a prime factor of i if (i % j == 0 and isPrime(j)) : sum += j return sum # Driver code if __name__ == "__main__": l = 18 r = 25 print(sum(l, r)) # This code is contributed by ita_c
C#
// C# program to find the sum
// of prime factors of all
// numbers in range [L-R]
using System;
class GFG
{
static bool isPrime(int n)
{
for (int i = 2;
i * i <= n; i++)
{
// n has a factor,
// hence not a prime
if (n % i == 0)
return false;
}
// we reach here if n has
// no factors and hence n
// is a prime number
return true;
}
static int sum(int l, int r)
{
int sum = 0;
// iterate from lower to upper
for (int i = l; i <= r; i++)
{
// if i is prime, it
// has no factors
if (isPrime(i))
continue;
for (int j = 2; j < i; j++)
{
// check if j is a
// prime factor of i
if (i % j == 0 && isPrime(j))
sum += j;
}
}
return sum;
}
// Driver code
public static void Main()
{
int l = 18, r = 25;
Console.WriteLine(sum(l, r));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP program to find the
// sum of prime factors of
// all numbers in range [L-R]
function isPrime($n)
{
for ($i = 2; $i * $i <= $n; $i++)
{
// n has a factor, hence
// not a prime
if ($n % $i == 0)
return false;
}
// we reach here if n has
// no factors and hence n
// is a prime number
return true;
}
function sum1($l, $r)
{
$sum = 0;
// iterate from lower to upper
for ($i = $l; $i <= $r; $i++)
{
// if i is prime, it
// has no factors
if (isPrime($i))
continue;
for ($j = 2; $j < $i; $j++)
{
// check if j is a
// prime factor of i
if ($i % $j == 0 && isPrime($j))
$sum += $j;
}
}
return $sum;
}
// Driver Code
$l = 18;
$r = 25;
echo sum1($l, $r);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find the sum of prime
// factors of all numbers in range [L-R]
function isPrime(n)
{
for (let i = 2; i * i <= n; i++) {
// n has a factor, hence not a prime
if (n % i == 0)
return false;
}
// we reach here if n has no factors
// and hence n is a prime number
return true;
}
function sum(l,r)
{
let sum = 0;
// iterate from lower to upper
for (let i = l; i <= r; i++) {
// if i is prime, it has no factors
if (isPrime(i))
continue;
for (let j = 2; j < i; j++) {
// check if j is a prime factor of i
if (i % j == 0 && isPrime(j))
sum += j;
}
}
return sum;
}
// Driver code
let l = 18, r = 25;
document.write(sum(l, r));
// This code is contributed by rag2127
</script>
Producción:
45
Complejidad de tiempo: O(N * N * sqrt(N))
Un enfoque eficiente es modificar ligeramente la criba de Eratóstenes para encontrar la suma de todos los divisores primos . A continuación, mantenga una array de prefijos para mantener la suma de la suma de todos los divisores primos hasta el índice i. Por lo tanto, pref_arr[r] – pref_arr[l-1] daría la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the sum of prime
// factors of all numbers in range [L-R]
#include<bits/stdc++.h>
using namespace std;
#define N 10000
long arr[N];
// function to compute the sieve
void sieve()
{
for (int i = 2; i * i < N; i++)
{
// i is prime
if (arr[i] == 0)
{
// add i to all the multiples of i till N
for (int j = 2; i * j < N; j++)
{
arr[i * j] += i;
}
}
}
}
// function that returns the sum
long sum(int l, int r)
{
// Function call to compute sieve
sieve();
// prefix array to keep the
// sum of all arr[i] till i
long pref_arr[r+1];
pref_arr[0] = arr[0];
// calculate the prefix sum of prime divisors
for (int i = 1; i <= r; i++) {
pref_arr[i] = pref_arr[i - 1] + arr[i];
}
// lower is the beginning of array
if (l == 1)
return (pref_arr[r]);
// lower is not the beginning of the array
else
return (pref_arr[r] - pref_arr[l - 1]);
}
// Driver Code
int main()
{
int l = 5, r = 10;
cout<<(sum(l, r));
return 0;
}
// This code is contributed by Rajput-Ji
Java
// Java program to find the sum of prime
// factors of all numbers in range [L-R]
public class gfg {
static int N = 10000;
static long arr[] = new long[N];
// function to compute the sieve
static void sieve()
{
for (int i = 2; i * i < N; i++) {
// i is prime
if (arr[i] == 0) {
// add i to all the multiples of i till N
for (int j = 2; i * j < N; j++) {
arr[i * j] += i;
}
}
}
}
// function that returns the sum
static long sum(int l, int r)
{
// Function call to compute sieve
sieve();
// prefix array to keep the sum of all arr[i] till i
long[] pref_arr = new long[r + 1];
pref_arr[0] = arr[0];
// calculate the prefix sum of prime divisors
for (int i = 1; i <= r; i++) {
pref_arr[i] = pref_arr[i - 1] + arr[i];
}
// lower is the beginning of array
if (l == 1)
return (pref_arr[r]);
// lower is not the beginning of the array
else
return (pref_arr[r] - pref_arr[l - 1]);
}
// Driver Code
public static void main(String[] args)
{
int l = 5, r = 10;
System.out.println(sum(l, r));
}
}
Python3
# Python3 program to find the sum of prime # factors of all numbers in range [L-R] N = 10000; arr = [0] * N; # function to compute the sieve def sieve(): i = 2; while(i * i < N): # i is prime if (arr[i] == 0): # add i to all the multiple # of i till N j = 2; while (i * j < N): arr[i * j] += i; j += 1; i += 1; # function that returns the sum def sum(l, r): # Function call to compute sieve sieve(); # prefix array to keep the # sum of all arr[i] till i pref_arr = [0] * (r + 1); pref_arr[0] = arr[0]; # calculate the prefix sum # of prime divisors for i in range(1, r + 1): pref_arr[i] = pref_arr[i - 1] + arr[i]; # lower is the beginning of array if (l == 1): return (pref_arr[r]); # lower is not the beginning # of the array else: return (pref_arr[r] - pref_arr[l - 1]); # Driver Code l = 5; r = 10; print(sum(l, r)); # This code is contributed by mits
C#
// C# program to find the sum
// of prime factors of all
// numbers in range [L-R]
using System;
class GFG
{
static int N = 10000;
static long[] arr = new long[N];
// function to compute
// the sieve
static void sieve()
{
for (int i = 2; i * i < N; i++)
{
// i is prime
if (arr[i] == 0)
{
// add i to all the multiples
// of i till N
for (int j = 2;
i * j < N; j++)
{
arr[i * j] += i;
}
}
}
}
// function that
// returns the sum
static long sum(int l, int r)
{
// Function call to
// compute sieve
sieve();
// prefix array to keep the
// sum of all arr[i] till i
long[] pref_arr = new long[r + 1];
pref_arr[0] = arr[0];
// calculate the prefix
// sum of prime divisors
for (int i = 1; i <= r; i++)
{
pref_arr[i] = pref_arr[i - 1] +
arr[i];
}
// lower is the beginning
// of array
if (l == 1)
return (pref_arr[r]);
// lower is not the
// beginning of the array
else
return (pref_arr[r] -
pref_arr[l - 1]);
}
// Driver Code
public static void Main()
{
int l = 5, r = 10;
Console.WriteLine(sum(l, r));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP program to find the sum of prime
// factors of all numbers in range [L-R]
$N = 10000;
$arr = array_fill(0, $N, 0);
// function to compute the sieve
function sieve()
{
global $N, $arr;
for ($i = 2; $i * $i < $N; $i++)
{
// i is prime
if ($arr[$i] == 0)
{
// add i to all the multiples
// of i till N
for ($j = 2; $i * $j < $N; $j++)
{
$arr[$i * $j] += $i;
}
}
}
}
// function that returns the sum
function sum($l, $r)
{
global $arr;
// Function call to compute sieve
sieve();
// prefix array to keep the
// sum of all arr[i] till i
$pref_arr = array_fill(0, $r + 1, 0);
$pref_arr[0] = $arr[0];
// calculate the prefix sum
// of prime divisors
for ($i = 1; $i <= $r; $i++)
{
$pref_arr[$i] = $pref_arr[$i - 1] +
$arr[$i];
}
// lower is the beginning of array
if ($l == 1)
return ($pref_arr[$r]);
// lower is not the beginning
// of the array
else
return ($pref_arr[$r] -
$pref_arr[$l - 1]);
}
// Driver Code
$l = 5;
$r = 10;
echo(sum($l, $r));
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find the sum of prime
// factors of all numbers in range [L-R]
let N = 10000;
let arr=new Array(N);
for(let i=0;i<N;i++)
{
arr[i]=0;
}
// function to compute the sieve
function sieve()
{
for (let i = 2; i * i < N; i++) {
// i is prime
if (arr[i] == 0) {
// add i to all the multiples of i till N
for (let j = 2; i * j < N; j++) {
arr[i * j] += i;
}
}
}
}
// function that returns the sum
function sum(l,r)
{
// Function call to compute sieve
sieve();
// prefix array to keep the sum of all arr[i] till i
let pref_arr = new Array(r + 1);
pref_arr[0] = arr[0];
// calculate the prefix sum of prime divisors
for (let i = 1; i <= r; i++) {
pref_arr[i] = pref_arr[i - 1] + arr[i];
}
// lower is the beginning of array
if (l == 1)
return (pref_arr[r]);
// lower is not the beginning of the array
else
return (pref_arr[r] - pref_arr[l - 1]);
}
// Driver Code
let l = 5, r = 10;
document.write(sum(l, r));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
17