给定一个范围，任务是找到给定范围内的数字计数，使其数字之和等于其所有素数数字之和。 例如：
null
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
方法： 一个有效的解决方案是修改 埃拉托斯坦筛 这样，对于每个非素数，它存储最小的素数因子（预因子）。
- 预处理为2和MAXN之间的所有数字找到最小的素数因子。这可以通过在恒定时间内将数分解为素数因子来实现，因为对于每个数，如果它是素数，则没有前置因子。
- 否则，我们可以把它分解成素数因子和数的另一部分，它可能是素数，也可能不是素数。
- 重复这个提取因子的过程，直到它变成素数。
- 然后，通过将最小素数因子的th位相加，检查该数字的位数是否等于素数因子的位数，即
SPF[n]的位数和+SPF[n]的位数和
- 现在，制作前缀和数组，计算有多少个有效数字，直到一个数字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 |
Javascript
<script> // Javascript 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 var MAXN = 100005; // array to store smallest // prime factor of number var spf = Array.from({length: MAXN}, (_, i) => 0); // array to store sum // of digits of a number var sum_digits = Array.from({length: MAXN}, (_, i) => 0); // boolean array to check // given number is countable // for required answer or not. var isValid = Array.from({length: MAXN}, (_, i) => false ); // prefix array to store answer var ans = Array.from({length: MAXN}, (_, i) => 0); // Calculating SPF (Smallest // Prime Factor) for every // number till MAXN. function Smallest_prime_factor() { // marking smallest prime factor // for every number to be itself. for (i = 1; i < MAXN; i++) spf[i] = i; // separately marking spf // for every even number as 2 for (i = 4; i < MAXN; i += 2) spf[i] = 2; for (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 (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 function Digit_Sum(copy) { var d = 0; while (copy > 0) { d += copy % 10; copy = parseInt(copy/10); } return d; } // find sum of digits of // all numbers up to MAXN function Sum_Of_All_Digits() { for (n = 2; n < MAXN; n++) { // add sum of digits of least // prime factor and n/spf[n] sum_digits[n] = sum_digits[parseInt(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 = 2; n < MAXN; n++) { if (isValid[n]) ans[n] = 1; ans[n] += ans[n - 1]; } } // Driver code Smallest_prime_factor(); Sum_Of_All_Digits(); // declaration var l, r; // print answer for required range l = 2; r = 3; document.write( "Valid numbers in the range " + l + " " + r + " are " + (ans[r] - ans[l - 1] )); // print answer for required range l = 2; r = 10; document.write( "<br>Valid numbers in the range " + l + " " + r + " are " + (ans[r] - ans[l - 1])); // This code contributed by shikhasingrajput </script> |
输出：
Valid numbers in the range 2 3 are 2 Valid numbers in the range 2 10 are 5
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
