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

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

本文概述

给定一个范围, 任务是找到给定范围内的数字计数, 以使其位数之和等于其所有素数位数之和。

例子：

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

方法：一个有效的解决方案是修改Eratosthenes筛这样, 对于每个非素数, 它都会存储最小的素因数(前置因子)。

预处理以找到2到MAXN之间所有数字的最小素因数。可以通过在固定时间内将数字分解为其质数因子来完成, 因为对于每个数字, 如果它是质数, 则没有前置因子。

否则, 我们可以将其分解为一个质数因子, 然后将其分解为质数因子的另一部分。

并重复此提取因子的过程, 直到它成为素数。

然后通过添加最小素数的第th个数字来检查该数字的位数是否等于素数的位数。

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

现在创建前缀求和数组, 该数组计算最多有N个数字的有效数字。对于每个查询, 请打印：

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
//for required answer or not.
bool isValid[MAXN] = { 0 };
  
//prefix array to store answer
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 ;
     }
  
     //prefix sum to compute answer
     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;
  
     //print answer for required range
     l = 2, r = 3;
     cout <<"Valid numbers in the range " <<l <<" " 
          <<r <<" are " <<ans[r] - ans[l - 1] <<endl;
  
     //print answer for required range
     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
//for required answer or not.
static boolean isValid[] = new boolean [MAXN];
  
//prefix array to store answer
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 ;
     }
  
     //prefix sum to compute answer
     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;
      
     //print answer for required range
     l = 2 ; r = 3 ;
     System.out.println( "Valid numbers in the range " + 
                                l + " " + r + " are " + 
                               (ans[r] - ans[l - 1 ] ));
      
     //print answer for required range
     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
//for required answer or not.
static bool []isValid = new bool [MAXN];
  
//prefix array to store answer
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 ;
     }
  
     //prefix sum to compute answer
     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;
      
     //print answer for required range
     l = 2; r = 3;
     Console.WriteLine( "Valid numbers in the range " + 
                               l + " " + r + " are " + 
                              (ans[r] - ans[l - 1] ));
      
     //print answer for required range
     l = 2; r = 10;
     Console.WriteLine( "Valid numbers in the range " + 
                               l + " " + r + " are " + 
                               (ans[r] - ans[l - 1]));
}
}
  
//This code is contributed
//by Subhadeep

输出如下：

Valid numbers in the range 2 3 are 2
Valid numbers in the range 2 10 are 5
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: