# 数字和等于其所有素数的数字之和的数字

2021年4月22日15:15:22 发表评论 1,011 次浏览

## 本文概述

Input: l = 2, r = 10
Output: 5
2, 3, 4, 5 and 7 are such numbers

Input: l = 15, r = 22
Output: 3
17, 19 and 22 are such numbers
As, 17 and 19 are already prime.
Prime Factors of 22 = 2 * 11 i.e
For 22, Sum of digits is 2+2 = 4
For 2 * 11, Sum of digits is 2 + 1 + 1 = 4

SPF [n]的Digits_Sum和(n/SPF [n])的Digits_Sum

ans [R] – ans [L-1]

## C ++

//C++ program to Find the count of the numbers
//in the given range such that the sum of its
//digit is equal to the sum of all its prime
//factors digits sum.
#include <bits/stdc++.h>
using namespace std;

//maximum size of number
#define MAXN 100005

//array to store smallest prime factor of number
int spf[MAXN] = { 0 };

//array to store sum of digits of a number
int sum_digits[MAXN] = { 0 };

//boolean array to check given number is countable
bool isValid[MAXN] = { 0 };

int ans[MAXN] = { 0 };

//Calculating SPF (Smallest Prime Factor) for every
//number till MAXN.
void Smallest_prime_factor()
{
//marking smallest prime factor for every
//number to be itself.
for ( int i = 1; i <MAXN; i++)
spf[i] = i;

//separately marking spf for every even
//number as 2
for ( int i = 4; i <MAXN; i += 2)
spf[i] = 2;

for ( int i = 3; i * i <= MAXN; i += 2)

//checking if i is prime
if (spf[i] == i)

//marking SPF for all numbers divisible by i
for ( int j = i * i; j <MAXN; j += i)

//marking spf[j] if it is not
//previously marked
if (spf[j] == j)
spf[j] = i;
}

//Function to find sum of digits in a number
int Digit_Sum( int copy)
{
int d = 0;
while (copy) {
d += copy % 10;
copy /= 10;
}

return d;
}

//find sum of digits of all numbers up to MAXN
void Sum_Of_All_Digits()
{
for ( int n = 2; n <MAXN; n++) {
//add sum of digits of least
//prime factor and n/spf[n]
sum_digits[n] = sum_digits[n /spf[n]]
+ Digit_Sum(spf[n]);

//if it is valid make isValid true
if (Digit_Sum(n) == sum_digits[n])
isValid[n] = true ;
}

for ( int n = 2; n <MAXN; n++) {
if (isValid[n])
ans[n] = 1;
ans[n] += ans[n - 1];
}
}

//Driver code
int main()
{
Smallest_prime_factor();
Sum_Of_All_Digits();

//decleartion
int l, r;

l = 2, r = 3;
cout <<"Valid numbers in the range " <<l <<" "
<<r <<" are " <<ans[r] - ans[l - 1] <<endl;

l = 2, r = 10;
cout <<"Valid numbers in the range " <<l <<" "
<<r <<" are " <<ans[r] - ans[l - 1] <<endl;

return 0;
}

## Java

//Java program to Find the count
//of the numbers in the given
//range such that the sum of its
//digit is equal to the sum of
//all its prime factors digits sum.
import java.io.*;

class GFG
{

//maximum size of number
static int MAXN = 100005 ;

//array to store smallest
//prime factor of number
static int spf[] = new int [MAXN];

//array to store sum
//of digits of a number
static int sum_digits[] = new int [MAXN];

//boolean array to check
//given number is countable
static boolean isValid[] = new boolean [MAXN];

static int ans[] = new int [MAXN];

//Calculating SPF (Smallest
//Prime Factor) for every
//number till MAXN.
static void Smallest_prime_factor()
{
//marking smallest prime factor
//for every number to be itself.
for ( int i = 1 ; i <MAXN; i++)
spf[i] = i;

//separately marking spf
//for every even number as 2
for ( int i = 4 ; i <MAXN; i += 2 )
spf[i] = 2 ;

for ( int i = 3 ;
i * i <= MAXN; i += 2 )

//checking if i is prime
if (spf[i] == i)

//marking SPF for all
//numbers divisible by i
for ( int j = i * i;
j <MAXN; j += i)

//marking spf[j] if it
//is not previously marked
if (spf[j] == j)
spf[j] = i;
}

//Function to find sum
//of digits in a number
static int Digit_Sum( int copy)
{
int d = 0 ;
while (copy> 0 )
{
d += copy % 10 ;
copy /= 10 ;
}

return d;
}

//find sum of digits of
//all numbers up to MAXN
static void Sum_Of_All_Digits()
{
for ( int n = 2 ; n <MAXN; n++)
{
//add sum of digits of least
//prime factor and n/spf[n]
sum_digits[n] = sum_digits[n /spf[n]]
+ Digit_Sum(spf[n]);

//if it is valid make isValid true
if (Digit_Sum(n) == sum_digits[n])
isValid[n] = true ;
}

for ( int n = 2 ; n <MAXN; n++)
{
if (isValid[n])
ans[n] = 1 ;
ans[n] += ans[n - 1 ];
}
}

//Driver code
public static void main (String[] args)
{
Smallest_prime_factor();
Sum_Of_All_Digits();

//declaration
int l, r;

l = 2 ; r = 3 ;
System.out.println( "Valid numbers in the range " +
l + " " + r + " are " +
(ans[r] - ans[l - 1 ] ));

l = 2 ; r = 10 ;
System.out.println( "Valid numbers in the range " +
l + " " + r + " are " +
(ans[r] - ans[l - 1 ]));
}
}

//This code is contributed
//by Inder

## Python 3

# Python 3 program to Find the count of
# the numbers in the given range such
# that the sum of its digit is equal to
# the sum of all its prime factors digits sum.

# maximum size of number
MAXN = 100005

# array to store smallest prime
# factor of number
spf = [ 0 ] * MAXN

# array to store sum of digits of a number
sum_digits = [ 0 ] * MAXN

# boolean array to check given number
# is countable for required answer or not.
isValid = [ 0 ] * MAXN

# prefix array to store answer
ans = [ 0 ] * MAXN

# Calculating SPF (Smallest Prime Factor)
# for every number till MAXN.
def Smallest_prime_factor():

# marking smallest prime factor
# for every number to be itself.
for i in range ( 1 , MAXN):
spf[i] = i

# separately marking spf for
# every even number as 2
for i in range ( 4 , MAXN, 2 ):
spf[i] = 2

i = 3
while i * i <= MAXN:

# checking if i is prime
if (spf[i] = = i):

# marking SPF for all numbers
# divisible by i
for j in range (i * i, MAXN, i):

# marking spf[j] if it is not
# previously marked
if (spf[j] = = j):
spf[j] = i

i + = 2

# Function to find sum of digits
# in a number
def Digit_Sum(copy):

d = 0
while (copy) :
d + = copy % 10
copy //= 10

return d

# find sum of digits of all
# numbers up to MAXN
def Sum_Of_All_Digits():

for n in range ( 2 , MAXN) :

# add sum of digits of least
# prime factor and n/spf[n]
sum_digits[n] = (sum_digits[n //spf[n]] +
Digit_Sum(spf[n]))

# if it is valid make isValid true
if (Digit_Sum(n) = = sum_digits[n]):
isValid[n] = True

# prefix sum to compute answer
for n in range ( 2 , MAXN) :
if (isValid[n]):
ans[n] = 1
ans[n] + = ans[n - 1 ]

# Driver code
if __name__ = = "__main__" :

Smallest_prime_factor()
Sum_Of_All_Digits()

# print answer for required range
l = 2
r = 3
print ( "Valid numbers in the range" , l, r, "are" , ans[r] - ans[l - 1 ])

# print answer for required range
l = 2
r = 10
print ( "Valid numbers in the range" , l, r, "are" , ans[r] - ans[l - 1 ])

# This code is contributed by ita_c

## C#

//C# program to Find the count
//of the numbers in the given
//range such that the sum of its
//digit is equal to the sum of
//all its prime factors digits sum.
using System;

class GFG
{

//maximum size of number
static int MAXN = 100005;

//array to store smallest
//prime factor of number
static int []spf = new int [MAXN];

//array to store sum
//of digits of a number
static int []sum_digits = new int [MAXN];

//boolean array to check
//given number is countable
static bool []isValid = new bool [MAXN];

static int []ans = new int [MAXN];

//Calculating SPF (Smallest
//Prime Factor) for every
//number till MAXN.
static void Smallest_prime_factor()
{
//marking smallest prime factor
//for every number to be itself.
for ( int i = 1; i <MAXN; i++)
spf[i] = i;

//separately marking spf
//for every even number as 2
for ( int i = 4; i <MAXN; i += 2)
spf[i] = 2;

for ( int i = 3;
i * i <= MAXN; i += 2)

//checking if i is prime
if (spf[i] == i)

//marking SPF for all
//numbers divisible by i
for ( int j = i * i;
j <MAXN; j += i)

//marking spf[j] if it
//is not previously marked
if (spf[j] == j)
spf[j] = i;
}

//Function to find sum
//of digits in a number
static int Digit_Sum( int copy)
{
int d = 0;
while (copy> 0)
{
d += copy % 10;
copy /= 10;
}

return d;
}

//find sum of digits of
//all numbers up to MAXN
static void Sum_Of_All_Digits()
{
for ( int n = 2; n <MAXN; n++)
{
//add sum of digits of least
//prime factor and n/spf[n]
sum_digits[n] = sum_digits[n /spf[n]] +
Digit_Sum(spf[n]);

//if it is valid make
//isValid true
if (Digit_Sum(n) == sum_digits[n])
isValid[n] = true ;
}

for ( int n = 2; n <MAXN; n++)
{
if (isValid[n])
ans[n] = 1;
ans[n] += ans[n - 1];
}
}

//Driver code
public static void Main ()
{
Smallest_prime_factor();
Sum_Of_All_Digits();

//declaration
int l, r;

l = 2; r = 3;
Console.WriteLine( "Valid numbers in the range " +
l + " " + r + " are " +
(ans[r] - ans[l - 1] ));

l = 2; r = 10;
Console.WriteLine( "Valid numbers in the range " +
l + " " + r + " are " +
(ans[r] - ans[l - 1]));
}
}

//This code is contributed