给你两个数字a和b（1<=a，b<=10^8）和n。任务是找到a和b之间的所有数字，包括正好有n个不同的素数因子。该解决方案的设计应能有效地处理针对不同a和b值的多个查询，就像在竞争性编程中一样。 例如：
null
Input : a = 1, b = 10, n = 2Output : 2// Only 6 = 2*3 and 10 = 2*5 have exactly two // distinct prime factorsInput : a = 1, b = 100, n = 3Output: 8// only 30 = 2*3*5, 42 = 2*3*7, 60 = 2*2*3*5, 66 = 2*3*11,// 70 = 2*5*7, 78 = 2*3*13, 84 = 2*2*3*7 and 90 = 2*3*3*5 // have exactly three distinct prime factors
这个问题基本上是应用 分段筛 如我们所知，一个数的所有素数因子总是小于或等于该数的平方根，即：；sqrt（n）。所以我们生成所有小于或等于10^8的素数，并将它们存储在一个数组中。现在使用这个分段筛子，我们检查从a到b的每个数字，精确地得到n个素数因子。
C++
// C++ program to find numbers with exactly n distinct // prime factor numbers from a to b #include<bits/stdc++.h> using namespace std; // Stores all primes less than and equals to sqrt(10^8) = 10000 vector < int > primes; // Generate all prime numbers less than or equals to sqrt(10^8) // = 10000 using sieve of sundaram void segmentedSieve() { int n = 10000; // Square root of 10^8 // In general Sieve of Sundaram, produces primes smaller // than (2*x + 2) for a number given number x. // Since we want primes smaller than n=10^4, we reduce // n to half int nNew = (n-2)/2; // This array is used to separate numbers of the form // i+j+2ij from others where 1 <= i <= j bool marked[nNew + 1]; // Initialize all elements as not marked memset (marked, false , sizeof (marked)); // Main logic of Sundaram. Mark all numbers of the // form i + j + 2ij as true where 1 <= i <= j for ( int i=1; i<=nNew; i++) for ( int j=i; (i + j + 2*i*j) <= nNew; j++) marked[i + j + 2*i*j] = true ; // Since 2 is a prime number primes.push_back(2); // Remaining primes are of the form 2*i + 1 such that // marked[i] is false. for ( int i=1; i<=nNew; i++) if (marked[i] == false ) primes.push_back(2*i+1); } // Function to count all numbers from a to b having exactly // n prime factors int Nfactors( int a, int b, int n) { segmentedSieve(); // result --> all numbers between a and b having // exactly n prime factors int result = 0; // check for each number for ( int i=a; i<=b; i++) { // tmp --> stores square root of current number because // all prime factors are always less than and // equal to square root of given number // copy --> it holds the copy of current number int tmp = sqrt (i), copy = i; // count --> it counts the number of distinct prime // factors of number int count = 0; // check divisibility of 'copy' with each prime less // than 'tmp' and divide it until it is divisible by // current prime factor for ( int j=0; primes[j]<=tmp; j++) { if (copy%primes[j]==0) { // increment count for distinct prime count++; while (copy%primes[j]==0) copy = copy/primes[j]; } } // if number is completely divisible then at last // 'copy' will be 1 else 'copy' will be prime, so // increment count by one if (copy != 1) count++; // if number has exactly n distinct primes then // increment result by one if (count==n) result++; } return result; } // Driver program to run the case int main() { int a = 1, b = 100, n = 3; cout << Nfactors(a, b, n); return 0; } |
JAVA
// Java program to find numbers with exactly n distinct // prime factor numbers from a to b import java.util.*; class GFG { // Stores all primes less than and // equals to sqrt(10^8) = 10000 static ArrayList<Integer> primes = new ArrayList<Integer>(); // Generate all prime numbers less // than or equals to sqrt(10^8) // = 10000 using sieve of sundaram static void segmentedSieve() { int n = 10000 ; // Square root of 10^8 // In general Sieve of Sundaram, // produces primes smaller // than (2*x + 2) for a number // given number x. Since we want // primes smaller than n=10^4, // we reduce n to half int nNew = (n - 2 )/ 2 ; // This array is used to separate // numbers of the form i+j+2ij // from others where 1 <= i <= j boolean [] marked= new boolean [nNew + 1 ]; // Main logic of Sundaram. Mark all // numbers of the form i + j + 2ij // as true where 1 <= i <= j for ( int i = 1 ; i <= nNew; i++) for ( int j = i; (i + j + 2 * i * j) <= nNew; j++) marked[i + j + 2 * i * j] = true ; // Since 2 is a prime number primes.add( 2 ); // Remaining primes are of the form 2*i + 1 such that // marked[i] is false. for ( int i = 1 ; i <= nNew; i++) if (marked[i] == false ) primes.add( 2 * i + 1 ); } // Function to count all numbers from a to b having exactly // n prime factors static int Nfactors( int a, int b, int n) { segmentedSieve(); // result --> all numbers between a and b having // exactly n prime factors int result = 0 ; // check for each number for ( int i = a; i <= b; i++) { // tmp --> stores square root of current number because // all prime factors are always less than and // equal to square root of given number // copy --> it holds the copy of current number int tmp = ( int )Math.sqrt(i), copy = i; // count --> it counts the number of distinct prime // factors of number int count = 0 ; // check divisibility of 'copy' with each prime less // than 'tmp' and divide it until it is divisible by // current prime factor for ( int j = 0 ; primes.get(j) <= tmp; j++) { if (copy % primes.get(j) == 0 ) { // increment count for distinct prime count++; while (copy % primes.get(j) == 0 ) copy = copy/primes.get(j); } } // if number is completely divisible then at last // 'copy' will be 1 else 'copy' will be prime, so // increment count by one if (copy != 1 ) count++; // if number has exactly n distinct primes then // increment result by one if (count == n) result++; } return result; } // Driver code public static void main (String[] args) { int a = 1 , b = 100 , n = 3 ; System.out.println(Nfactors(a, b, n)); } } // This code is contributed by chandan_jnu |
Python3
# Python3 program to find numbers with # exactly n distinct prime factor numbers # from a to b import math # Stores all primes less than and # equals to sqrt(10^8) = 10000 primes = []; # Generate all prime numbers less than # or equals to sqrt(10^8) = 10000 # using sieve of sundaram def segmentedSieve(): n = 10000 ; # Square root of 10^8 # In general Sieve of Sundaram, produces # primes smaller than (2*x + 2) for a # given number x. Since we want primes # smaller than n=10^4, we reduce n to half nNew = int ((n - 2 ) / 2 ); # This array is used to separate # numbers of the form i+j+2ij # from others where 1 <= i <= j marked = [ False ] * (nNew + 1 ); # Main logic of Sundaram. Mark all # numbers of the form i + j + 2ij # as true where 1 <= i <= j for i in range ( 1 , nNew + 1 ): j = i; while ((i + j + 2 * i * j) < = nNew): marked[i + j + 2 * i * j] = True ; j + = 1 ; # Since 2 is a prime number primes.append( 2 ); # Remaining primes are of the # form 2*i + 1 such that # marked[i] is false. for i in range ( 1 , nNew + 1 ): if (marked[i] = = False ): primes.append( 2 * i + 1 ); # Function to count all numbers # from a to b having exactly n # prime factors def Nfactors(a, b, n): segmentedSieve(); # result --> all numbers between # a and b having exactly n prime # factors result = 0 ; # check for each number for i in range (a, b + 1 ): # tmp --> stores square root of # current number because all prime # factors are always less than and # equal to square root of given number # copy --> it holds the copy of # current number tmp = math.sqrt(i); copy = i; # count --> it counts the number of # distinct prime factors of number count = 0 ; # check divisibility of 'copy' with # each prime less than 'tmp' and # divide it until it is divisible # by current prime factor j = 0 ; while (primes[j] < = tmp): if (copy % primes[j] = = 0 ): # increment count for # distinct prime count + = 1 ; while (copy % primes[j] = = 0 ): copy = (copy / / primes[j]); j + = 1 ; # if number is completely divisible # then at last 'copy' will be 1 else # 'copy' will be prime, so increment # count by one if (copy ! = 1 ): count + = 1 ; # if number has exactly n distinct # primes then increment result by one if (count = = n): result + = 1 ; return result; # Driver Code a = 1 ; b = 100 ; n = 3 ; print (Nfactors(a, b, n)); # This code is contributed # by chandan_jnu |
C#
// C# program to find numbers with exactly n // distinct prime factor numbers from a to b using System; using System.Collections; class GFG { // Stores all primes less than and // equals to sqrt(10^8) = 10000 static ArrayList primes = new ArrayList(); // Generate all prime numbers less // than or equals to sqrt(10^8) // = 10000 using sieve of sundaram static void segmentedSieve() { int n = 10000; // Square root of 10^8 // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a number // given number x. Since we want primes // smaller than n=10^4, we reduce n to half int nNew = (n - 2) / 2; // This array is used to separate // numbers of the form i+j+2ij // from others where 1 <= i <= j bool [] marked = new bool [nNew + 1]; // Main logic of Sundaram. Mark all // numbers of the form i + j + 2ij // as true where 1 <= i <= j for ( int i = 1; i <= nNew; i++) for ( int j = i; (i + j + 2 * i * j) <= nNew; j++) marked[i + j + 2 * i * j] = true ; // Since 2 is a prime number primes.Add(2); // Remaining primes are of the form // 2*i + 1 such that marked[i] is false. for ( int i = 1; i <= nNew; i++) if (marked[i] == false ) primes.Add(2 * i + 1); } // Function to count all numbers from // a to b having exactly n prime factors static int Nfactors( int a, int b, int n) { segmentedSieve(); // result --> all numbers between a and b // having exactly n prime factors int result = 0; // check for each number for ( int i = a; i <= b; i++) { // tmp --> stores square root of current // number because all prime factors are // always less than and equal to square // root of given number // copy --> it holds the copy of current number int tmp = ( int )Math.Sqrt(i), copy = i; // count --> it counts the number of // distinct prime factors of number int count = 0; // check divisibility of 'copy' with each // prime less than 'tmp' and divide it until // it is divisible by current prime factor for ( int j = 0; ( int )primes[j] <= tmp; j++) { if (copy % ( int )primes[j] == 0) { // increment count for distinct prime count++; while (copy % ( int )primes[j] == 0) copy = copy / ( int )primes[j]; } } // if number is completely divisible then // at last 'copy' will be 1 else 'copy' // will be prime, so increment count by one if (copy != 1) count++; // if number has exactly n distinct // primes then increment result by one if (count == n) result++; } return result; } // Driver code public static void Main() { int a = 1, b = 100, n = 3; Console.WriteLine(Nfactors(a, b, n)); } } // This code is contributed by mits |
PHP
<?php // PHP program to find numbers with exactly n // distinct prime factor numbers from a to b // Stores all primes less than and equals // to sqrt(10^8) = 10000 $primes = array (); // Generate all prime numbers less than or // equals to sqrt(10^8) = 10000 using // sieve of sundaram function segmentedSieve() { global $primes ; $n = 10000; // Square root of 10^8 // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a // given number x. Since we want primes // smaller than n=10^4, we reduce n to half $nNew = (int)(( $n -2)/2); // This array is used to separate numbers of // the form i+j+2ij from others where 1 <= i <= j $marked = array_fill (0, $nNew + 1, false); // Main logic of Sundaram. Mark all numbers of the // form i + j + 2ij as true where 1 <= i <= j for ( $i = 1; $i <= $nNew ; $i ++) for ( $j = $i ; ( $i + $j + 2 * $i * $j ) <= $nNew ; $j ++) $marked [ $i + $j + 2 * $i * $j ] = true; // Since 2 is a prime number array_push ( $primes , 2); // Remaining primes are of the form 2*i + 1 // such that marked[i] is false. for ( $i = 1; $i <= $nNew ; $i ++) if ( $marked [ $i ] == false) array_push ( $primes , 2 * $i + 1); } // Function to count all numbers from a to b // having exactly n prime factors function Nfactors( $a , $b , $n ) { global $primes ; segmentedSieve(); // result --> all numbers between a and b // having exactly n prime factors $result = 0; // check for each number for ( $i = $a ; $i <= $b ; $i ++) { // tmp --> stores square root of current // number because all prime factors are // always less than and equal to square // root of given number // copy --> it holds the copy of current number $tmp = sqrt( $i ); $copy = $i ; // count --> it counts the number of // distinct prime factors of number $count = 0; // check divisibility of 'copy' with each // prime less than 'tmp' and divide it until // it is divisible by current prime factor for ( $j = 0; $primes [ $j ] <= $tmp ; $j ++) { if ( $copy % $primes [ $j ] == 0) { // increment count for distinct prime $count ++; while ( $copy % $primes [ $j ] == 0) $copy = (int)( $copy / $primes [ $j ]); } } // if number is completely divisible then // at last 'copy' will be 1 else 'copy' // will be prime, so increment count by one if ( $copy != 1) $count ++; // if number has exactly n distinct primes // then increment result by one if ( $count == $n ) $result ++; } return $result ; } // Driver Code $a = 1; $b = 100; $n = 3; print (Nfactors( $a , $b , $n )); // This code is contributed by chandan_jnu ?> |
Javascript
<script> // JavaScript program to find numbers with exactly n // distinct prime factor numbers from a to b // Stores all primes less than and // equals to sqrt(10^8) = 10000 let primes = []; // Generate all prime numbers less // than or equals to sqrt(10^8) // = 10000 using sieve of sundaram function segmentedSieve() { let n = 10000; // Square root of 10^8 // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a number // given number x. Since we want primes // smaller than n=10^4, we reduce n to half let nNew = parseInt((n - 2) / 2, 10); // This array is used to separate // numbers of the form i+j+2ij // from others where 1 <= i <= j let marked = new Array(nNew + 1); marked.fill( false ); // Main logic of Sundaram. Mark all // numbers of the form i + j + 2ij // as true where 1 <= i <= j for (let i = 1; i <= nNew; i++) for (let j = i; (i + j + 2 * i * j) <= nNew; j++) marked[i + j + 2 * i * j] = true ; // Since 2 is a prime number primes.push(2); // Remaining primes are of the form // 2*i + 1 such that marked[i] is false. for (let i = 1; i <= nNew; i++) if (marked[i] == false ) primes.push(2 * i + 1); } // Function to count all numbers from // a to b having exactly n prime factors function Nfactors(a, b, n) { segmentedSieve(); // result --> all numbers between a and b // having exactly n prime factors let result = 0; // check for each number for (let i = a; i <= b; i++) { // tmp --> stores square root of current // number because all prime factors are // always less than and equal to square // root of given number // copy --> it holds the copy of current number let tmp = parseInt(Math.sqrt(i), 10), copy = i; // count --> it counts the number of // distinct prime factors of number let count = 0; // check divisibility of 'copy' with each // prime less than 'tmp' and divide it until // it is divisible by current prime factor for (let j = 0; primes[j] <= tmp; j++) { if (copy % primes[j] == 0) { // increment count for distinct prime count++; while (copy % primes[j] == 0) copy = parseInt(copy / primes[j], 10); } } // if number is completely divisible then // at last 'copy' will be 1 else 'copy' // will be prime, so increment count by one if (copy != 1) count++; // if number has exactly n distinct // primes then increment result by one if (count == n) result++; } return result; } let a = 1, b = 100, n = 3; document.write(Nfactors(a, b, n)); </script> |
输出：
8
如果你有其他方法来解决这个问题，请在评论中分享。 本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
