Dado un número N. La tarea es encontrar la suma de todos los divisores primos de N.
Ejemplos:
Input: 60 Output: 10 2, 3, 5 are prime divisors of 60 Input: 39 Output: 16 3, 13 are prime divisors of 39
Un enfoque ingenuo será iterar para todos los números hasta N y verificar si el número divide a N. Si el número divide a N, verifique si ese número es primo o no. Suma todos los números primos hasta N que divide a N.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find sum of
// prime divisors of N
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
// Function to check if the
// number is prime or not.
bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// function to find sum of prime
// divisors of N
int SumOfPrimeDivisors(int n)
{
int sum = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
if (isPrime(i))
sum += i;
}
}
return sum;
}
// Driver code
int main()
{
int n = 60;
cout << "Sum of prime divisors of 60 is " << SumOfPrimeDivisors(n) << endl;
}
C
// C program to find sum of
// prime divisors of N
#include <stdio.h>
#include <stdbool.h>
#define N 1000005
// Function to check if the
// number is prime or not.
bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// function to find sum of prime
// divisors of N
int SumOfPrimeDivisors(int n)
{
int sum = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
if (isPrime(i))
sum += i;
}
}
return sum;
}
// Driver code
int main()
{
int n = 60;
printf("Sum of prime divisors of 60 is %d\n",SumOfPrimeDivisors(n));
}
// This code is contributed by kothavvsaakash.
Java
// Java program to find sum
// of prime divisors of N
import java.io.*;
import java.util.*;
class GFG
{
// Function to check if the
// number is prime or not.
static boolean isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that
// we can skip middle five
// numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5;
i * i <= n; i = i + 6)
if (n % i == 0 ||
n % (i + 2) == 0)
return false;
return true;
}
// function to find
// sum of prime
// divisors of N
static int SumOfPrimeDivisors(int n)
{
int sum = 0;
for (int i = 1;
i <= n; i++)
{
if (n % i == 0)
{
if (isPrime(i))
sum += i;
}
}
return sum;
}
// Driver code
public static void main(String args[])
{
int n = 60;
System.out.print("Sum of prime divisors of 60 is " +
SumOfPrimeDivisors(n) + "\n");
}
}
C#
// C# program to find sum
// of prime divisors of N
using System;
class GFG
{
// Function to check if the
// number is prime or not.
static bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that
// we can skip middle five
// numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5;
i * i <= n; i = i + 6)
if (n % i == 0 ||
n % (i + 2) == 0)
return false;
return true;
}
// function to find
// sum of prime
// divisors of N
static int SumOfPrimeDivisors(int n)
{
int sum = 0;
for (int i = 1;
i <= n; i++)
{
if (n % i == 0)
{
if (isPrime(i))
sum += i;
}
}
return sum;
}
// Driver code
public static void Main()
{
int n = 60;
Console.WriteLine("Sum of prime divisors of 60 is " +
SumOfPrimeDivisors(n) + "\n");
}
}
// This code is contributed
// by inder_verma.
Python3
# Python 3 program to find
# sum of prime divisors of N
N = 1000005
# Function to check if the
# number is prime or not.
def isPrime(n):
# Corner cases
if n <= 1:
return False
if n <= 3:
return True
# This is checked so that
# we can skip middle five
# numbers in below loop
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if (n % i == 0 or
n % (i + 2) == 0):
return False
i = i + 6
return True
# function to find sum
# of prime divisors of N
def SumOfPrimeDivisors(n):
sum = 0
for i in range(1, n + 1) :
if n % i == 0 :
if isPrime(i):
sum += i
return sum
# Driver code
n = 60
print("Sum of prime divisors of 60 is " +
str(SumOfPrimeDivisors(n)))
# This code is contributed
# by ChitraNayal
PHP
<?php
// PHP program to find sum
// of prime divisors of N
$N = 1000005;
// Function to check if the
// number is prime or not.
function isPrime($n)
{
global $N;
// Corner cases
if ($n <= 1)
return false;
if ($n <= 3)
return true;
// This is checked so that
// we can skip middle five
// numbers in below loop
if ($n % 2 == 0 || $n % 3 == 0)
return false;
for ($i = 5; $i * $i <= $n;
$i = $i + 6)
if ($n % $i == 0 ||
$n % ($i + 2) == 0)
return false;
return true;
}
// function to find sum
// of prime divisors of N
function SumOfPrimeDivisors($n)
{
$sum = 0;
for ($i = 1; $i <= $n; $i++)
{
if ($n % $i == 0)
{
if (isPrime($i))
$sum += $i;
}
}
return $sum;
}
// Driver code
$n = 60;
echo "Sum of prime divisors of 60 is " .
SumOfPrimeDivisors($n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to find sum of
// prime divisors of N
let N = 1000005;
// Function to check if the
// number is prime or not.
function isPrime(n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (let i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// function to find sum of prime
// divisors of N
function SumOfPrimeDivisors(n)
{
let sum = 0;
for (let i = 1; i <= n; i++) {
if (n % i == 0) {
if (isPrime(i))
sum += i;
}
}
return sum;
}
// Driver code
let n = 60;
document.write("Sum of prime divisors of 60 is "+SumOfPrimeDivisors(n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Sum of prime divisors of 60 is 10
Complejidad de tiempo: O(N * sqrt(N))
Enfoque eficiente: la complejidad se puede reducir utilizando Tamiz de Eratóstenes con algunas modificaciones. Las modificaciones son las siguientes:
- Tome una array de tamaño N y sustituya cero en todos los índices (inicialmente considere que todos los números son primos).
- Iterar para todos los números cuyos índices tienen cero (es decir, son números primos).
- Suma este número a todos sus múltiplos menores que N
- Devuelve el valor de array[N] que tiene la suma almacenada en él.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find prime divisors of
// all numbers from 1 to n
#include <bits/stdc++.h>
using namespace std;
// function to find prime divisors of
// all numbers from 1 to n
int Sum(int N)
{
int SumOfPrimeDivisors[N+1] = { 0 };
for (int i = 2; i <= N; ++i) {
// if the number is prime
if (!SumOfPrimeDivisors[i]) {
// add this prime to all it's multiples
for (int j = i; j <= N; j += i) {
SumOfPrimeDivisors[j] += i;
}
}
}
return SumOfPrimeDivisors[N];
}
// Driver code
int main()
{
int N = 60;
cout << "Sum of prime divisors of 60 is "
<< Sum(N) << endl;
}
Java
// Java program to find
// prime divisors of
// all numbers from 1 to n
import java.io.*;
import java.util.*;
class GFG
{
// function to find prime
// divisors of all numbers
// from 1 to n
static int Sum(int N)
{
int SumOfPrimeDivisors[] = new int[N + 1];
for (int i = 2; i <= N; ++i)
{
// if the number is prime
if (SumOfPrimeDivisors[i] == 0)
{
// add this prime to
// all it's multiples
for (int j = i; j <= N; j += i)
{
SumOfPrimeDivisors[j] += i;
}
}
}
return SumOfPrimeDivisors[N];
}
// Driver code
public static void main(String args[])
{
int N = 60;
System.out.print("Sum of prime " +
"divisors of 60 is " +
Sum(N) + "\n");
}
}
Python3
# Python 3 program to find
# prime divisors of
# all numbers from 1 to n
# function to find prime
# divisors of all numbers
# from 1 to n
def Sum(N):
SumOfPrimeDivisors = [0] * (N + 1)
for i in range(2, N + 1) :
# if the number is prime
if (SumOfPrimeDivisors[i] == 0) :
# add this prime to
# all it's multiples
for j in range(i, N + 1, i) :
SumOfPrimeDivisors[j] += i
return SumOfPrimeDivisors[N]
# Driver code
N = 60
print("Sum of prime" ,
"divisors of 60 is",
Sum(N));
# This code is contributed
# by Smitha
C#
// C# program to find
// prime divisors of
// all numbers from 1 to n
using System;
class GFG
{
// function to find prime
// divisors of all numbers
// from 1 to n
static int Sum(int N)
{
int []SumOfPrimeDivisors = new int[N + 1];
for (int i = 2; i <= N; ++i)
{
// if the number is prime
if (SumOfPrimeDivisors[i] == 0)
{
// add this prime to
// all it's multiples
for (int j = i;
j <= N; j += i)
{
SumOfPrimeDivisors[j] += i;
}
}
}
return SumOfPrimeDivisors[N];
}
// Driver code
public static void Main()
{
int N = 60;
Console.Write("Sum of prime " +
"divisors of 60 is " +
Sum(N) + "\n");
}
}
// This code is contributed
// by Smitha
PHP
<?php
// PHP program to find prime
// divisors of all numbers
// from 1 to n
// function to find prime
// divisors of all numbers
// from 1 to n
function Sum($N)
{
for($i = 0; $i <= $N; $i++)
$SumOfPrimeDivisors[$i] = 0;
for ($i = 2; $i <= $N; ++$i)
{
// if the number is prime
if (!$SumOfPrimeDivisors[$i])
{
// add this prime to
// all it's multiples
for ($j = $i; $j <= $N; $j += $i)
{
$SumOfPrimeDivisors[$j] += $i;
}
}
}
return $SumOfPrimeDivisors[$N];
}
// Driver code
$N = 60;
echo "Sum of prime divisors of 60 is " . Sum($N);
// This code is contributed by Mahadev99
?>
Javascript
<script>
// Javascript program to find
// prime divisors of
// all numbers from 1 to n
// function to find prime
// divisors of all numbers
// from 1 to n
function Sum(N)
{
let SumOfPrimeDivisors = new Array(N+1);
for(let i=0;i<SumOfPrimeDivisors.length;i++)
{
SumOfPrimeDivisors[i]=0;
}
for (let i = 2; i <= N; ++i)
{
// if the number is prime
if (SumOfPrimeDivisors[i] == 0)
{
// add this prime to
// all it's multiples
for (let j = i; j <= N; j += i)
{
SumOfPrimeDivisors[j] += i;
}
}
}
return SumOfPrimeDivisors[N];
}
// Driver code
let N = 60;
document.write("Sum of prime " +
"divisors of 60 is " +
Sum(N) + "<br>");
// This code is contributed by rag2127
</script>
Producción
Sum of prime divisors of 60 is 10
Complejidad de tiempo: O(N * log N)
Enfoque eficiente:
La complejidad del tiempo se puede reducir encontrando todos los factores de manera eficiente.
El siguiente enfoque describe cómo encontrar todos los factores de manera eficiente.
Si nos fijamos bien, todos los divisores están presentes en pares. Por ejemplo, si n = 100, los distintos pares de divisores son: (1,100), (2,50), (4,25), (5,20), (10,10)
Usando este hecho podríamos acelerar nuestro programa significativamente.
Sin embargo, debemos tener cuidado si hay dos divisores iguales como en el caso de (10, 10). En tal caso, tomaríamos sólo uno de ellos.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find sum of
// prime divisors of N
#include <bits/stdc++.h>
using namespace std;
// Function to check if the
// number is prime or not.
bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// function to find sum of prime
// divisors of N
int SumOfPrimeDivisors(int n)
{
int sum = 0;
// return type of sqrt function
// if float
int root_n = (int)sqrt(n);
for (int i = 1; i <= root_n; i++) {
if (n % i == 0) {
// both factors are same
if (i == n / i && isPrime(i)) {
sum += i;
}
else {
// both factors are
// not same ( i and n/i )
if (isPrime(i)) {
sum += i;
}
if (isPrime(n / i)) {
sum += (n / i);
}
}
}
}
return sum;
}
// Driver code
int main()
{
int n = 60;
cout << "Sum of prime divisors of 60 is "
<< SumOfPrimeDivisors(n) << endl;
}
// This code is contributed by hemantraj712
C
// C program to find sum of
// prime divisors of N
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
// Function to check if the
// number is prime or not.
bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// function to find sum of prime
// divisors of N
int SumOfPrimeDivisors(int n)
{
int sum = 0;
// return type of sqrt function
// if float
int root_n = (int)sqrt(n);
for (int i = 1; i <= root_n; i++) {
if (n % i == 0) {
// both factors are same
if (i == n / i && isPrime(i)) {
sum += i;
}
else {
// both factors are
// not same ( i and n/i )
if (isPrime(i)) {
sum += i;
}
if (isPrime(n / i)) {
sum += (n / i);
}
}
}
}
return sum;
}
// Driver code
int main()
{
int n = 60;
printf("Sum of prime divisors of 60 is %d\n",SumOfPrimeDivisors(n));
}
// This code is contributed by hemantraj712
Java
// Java program to find sum of
// prime divisors of N
class GFG{
// Function to check if the
// number is prime or not.
static boolean isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for(int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function to find sum of prime
// divisors of N
static int SumOfPrimeDivisors(int n)
{
int sum = 0;
// Return type of sqrt function
// if float
int root_n = (int)Math.sqrt(n);
for(int i = 1; i <= root_n; i++)
{
if (n % i == 0)
{
// Both factors are same
if (i == n / i && isPrime(i))
{
sum += i;
}
else
{
// Both factors are
// not same ( i and n/i )
if (isPrime(i))
{
sum += i;
}
if (isPrime(n / i))
{
sum += (n / i);
}
}
}
}
return sum;
}
// Driver code
public static void main(String[] args)
{
int n = 60;
System.out.println("Sum of prime divisors of 60 is " +
SumOfPrimeDivisors(n));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to find sum of
# prime divisors of N
import math
# Function to check if the
# number is prime or not.
def isPrime(n) :
# Corner cases
if (n <= 1) :
return False
if (n <= 3) :
return True
# This is checked so that we can skip
# middle five numbers in below loop
if (n % 2 == 0 or n % 3 == 0) :
return False
i = 5
while i * i <= n :
if (n % i == 0 or n % (i + 2) == 0) :
return False
i = i + 6
return True
# function to find sum of prime
# divisors of N
def SumOfPrimeDivisors(n) :
Sum = 0
# return type of sqrt function
# if float
root_n = (int)(math.sqrt(n))
for i in range(1, root_n + 1) :
if (n % i == 0) :
# both factors are same
if (i == (int)(n / i) and isPrime(i)) :
Sum += i
else :
# both factors are
# not same ( i and n/i )
if (isPrime(i)) :
Sum += i
if (isPrime((int)(n / i))) :
Sum += (int)(n / i)
return Sum
n = 60
print("Sum of prime divisors of 60 is", SumOfPrimeDivisors(n))
# This code is contributed by rameshtravel07
C#
// C# program to find sum of
// prime divisors of N
using System;
class GFG {
// Function to check if the
// number is prime or not.
static bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// function to find sum of prime
// divisors of N
static int SumOfPrimeDivisors(int n)
{
int sum = 0;
// return type of sqrt function
// if float
int root_n = (int)Math.Sqrt(n);
for (int i = 1; i <= root_n; i++) {
if (n % i == 0) {
// both factors are same
if (i == n / i && isPrime(i)) {
sum += i;
}
else {
// both factors are
// not same ( i and n/i )
if (isPrime(i)) {
sum += i;
}
if (isPrime(n / i)) {
sum += (n / i);
}
}
}
}
return sum;
}
static void Main() {
int n = 60;
Console.WriteLine("Sum of prime divisors of 60 is " + SumOfPrimeDivisors(n));
}
}
// This code is contributed by suresh07.
Javascript
<script>
// Javascript program to find sum of
// prime divisors of N
// Function to check if the
// number is prime or not.
function isPrime(n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (let i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// function to find sum of prime
// divisors of N
function SumOfPrimeDivisors(n)
{
let sum = 0;
// return type of sqrt function
// if float
let root_n = parseInt(Math.sqrt(n), 10);
for (let i = 1; i <= root_n; i++) {
if (n % i == 0) {
// both factors are same
if (i == parseInt(n / i, 10) && isPrime(i)) {
sum += i;
}
else {
// both factors are
// not same ( i and n/i )
if (isPrime(i)) {
sum += i;
}
if (isPrime(parseInt(n / i, 10))) {
sum += (parseInt(n / i, 10));
}
}
}
}
return sum;
}
let n = 60;
document.write("Sum of prime divisors of 60 is "
+ SumOfPrimeDivisors(n) + "</br>");
// This code is contributed by muksh07.
</script>
Producción
Sum of prime divisors of 60 is 10
Complejidad de tiempo : O (sqrt (N) * sqrt (N))
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA