几乎素数-yiteyi-C++库

k-几乎素数是一个有k个素数因子的数（不一定不同）。

null

例如 ,

2, 3, 5, 7, 11 ….（事实上，所有素数）都是1-几乎素数，因为它们只有1个素数因子（即它们本身）。

4, 6, 9…. 是2-几乎素数，因为它们正好有2个素数因子（4=2*2，6=2*3，9=3*3）

同样，32是一个5-几乎素数（32=2*2*2*2*2），72也是（2*2*2*3*3）

所有1-几乎素数称为素数，所有2-几乎素数称为半素数。任务是打印前n个是k素数的数字。

例如：

Input: k = 2, n = 5Output: 4 6 9 10 144 has two prime factors, 2 x 26 has two prime factors, 2 x 3Similarly, 9(3 x 3), 10(2 x 5) and 14(2 x 7)Input: k = 10, n = 2Output: 1024 15361024 and 1536 are first two numbers with 10prime factors.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们迭代自然数并继续打印k-素数，直到打印的k-素数的计数小于或等于n 求素数如果计数是k，我们把这个数看作k-素数。

以下是上述方法的实施情况：

C++

                         // Program to print first n numbers that are k-primes                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // A function to count all prime factors of a given number                       
                         int                                     countPrimeFactors(                                     int                                     n)                       
                         {                       
                                                 int                                     count = 0;                       
           
                                                 // Count the number of 2s that divide n                       
                                                 while                                     (n%2 == 0)                       
                                                 {                       
                                                 n = n/2;                       
                                                 count++;                       
                                                 }                       
           
                                                 // n must be odd at this point. So we can skip one                       
                                                 // element (Note i = i +2)                       
                                                 for                                     (                                     int                                     i = 3; i <=                                     sqrt                                     (n); i = i+2)                       
                                                 {                       
                                                 // While i divides n, count i and divide n                       
                                                 while                                     (n%i == 0)                       
                                                 {                       
                                                 n = n/i;                       
                                                 count++;                       
                                                 }                       
                                                 }                       
           
                                                 // This condition is to handle the case when n is a                       
                                                 // prime number greater than 2                       
                                                 if                                     (n > 2)                       
                                                 count++;                       
           
                                                 return                                     (count);                       
                         }                       
           
                         // A function to print the first n numbers that are                       
                         // k-almost primes.                       
                         void                                     printKAlmostPrimes(                                     int                                     k,                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i=1, num=2; i<=n; num++)                       
                                                 {                       
                                                 // Print this number if it is k-prime                       
                                                 if                                     (countPrimeFactors(num) == k)                       
                                                 {                       
                                                 printf                                     (                                     "%d "                                     , num);                       
           
                                                 // Increment count of k-primes printed                       
                                                 // so far                       
                                                 i++;                       
                                                 }                       
                                                 }                       
                                                 return                                     ;                       
                         }                       
           
                         /* Driver program to test above function */                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 10, k = 2;                       
                                                 printf                                     (                                     "First %d %d-almost prime numbers : "                                     ,                       
                                                 n, k);                       
                                                 printKAlmostPrimes(k, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Program to print first n numbers that                       
                         // are k-primes                       
           
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // A function to count all prime factors                       
                                                 // of a given number                       
                                                 static                                     int                                     countPrimeFactors(                                     int                                     n)                       
                                                 {                       
           
                                                 int                                     count =                                     0                                     ;                       
           
                                                 // Count the number of 2s that divide n                       
                                                 while                                     (n %                                     2                                     ==                                     0                                     ) {                       
           
                                                 n = n /                                     2                                     ;                       
                                                 count++;                       
                                                 }                       
           
                                                 // n must be odd at this point. So we                       
                                                 // can skip one element (Note i = i +2)                       
                                                 for                                     (                                     int                                     i =                                     3                                     ; i <= Math.sqrt(n);                       
                                                 i = i +                                     2                                     ) {                       
           
                                                 // While i divides n, count i and                       
                                                 // divide n                       
                                                 while                                     (n % i ==                                     0                                     ) {                       
           
                                                 n = n / i;                       
                                                 count++;                       
                                                 }                       
                                                 }                       
           
                                                 // This condition is to handle the case                       
                                                 // when n is a prime number greater                       
                                                 // than 2                       
                                                 if                                     (n >                                     2                                     )                       
                                                 count++;                       
           
                                                 return                                     (count);                       
                                                 }                       
           
                                                 // A function to print the first n numbers                       
                                                 // that are k-almost primes.                       
                                                 static                                     void                                     printKAlmostPrimes(                                     int                                     k,                                     int                                     n)                       
                                                 {                       
           
                                                 for                                     (                                     int                                     i =                                     1                                     , num =                                     2                                     ; i <= n; num++) {                       
                                   
                                                 // Print this number if it is k-prime                       
                                                 if                                     (countPrimeFactors(num) == k) {                       
                                   
                                                 System.out.print(num +                                     " "                                     );                       
           
                                                 // Increment count of k-primes                       
                                                 // printed so far                       
                                                 i++;                       
                                                 }                       
                                                 }                       
           
                                                 return                                     ;                       
                                                 }                       
           
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     10                                     , k =                                     2                                     ;                       
                                                 System.out.println(                                     "First "                                     + n +                                     " "                       
                                                 + k +                                     "-almost prime numbers : "                                     );                       
           
                                                 printKAlmostPrimes(k, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

Python3

                         # Python3 Program to print first                       
                         # n numbers that are k-primes                       
                         import                                     math                       
           
                         # A function to count all prime                       
                         # factors of a given number                       
                         def                                     countPrimeFactors(n):                       
                                                 count                                     =                                     0                                     ;                       
           
                                                 # Count the number of                       
                                                 # 2s that divide n                       
                                                 while                                     (n                                     %                                     2                                     =                                     =                                     0                                     ):                       
                                                 n                                     =                                     n                                     /                                     2                                     ;                       
                                                 count                                     +                                     =                                     1                                     ;                       
           
                                                 # n must be odd at this point.                       
                                                 # So we can skip one                       
                                                 # element (Note i = i +2)                       
                                                 i                                     =                                     3                                     ;                       
                                                 while                                     (i <                                     =                                     math.sqrt(n)):                       
                                   
                                                 # While i divides n,                       
                                                 # count i and divide n                       
                                                 while                                     (n                                     %                                     i                                     =                                     =                                     0                                     ):                       
                                                 n                                     =                                     n                                     /                                     i;                       
                                                 count                                     +                                     =                                     1                                     ;                       
                                                 i                                     =                                     i                                     +                                     2                                     ;                       
           
                                                 # This condition is to handle                       
                                                 # the case when n is a                       
                                                 # prime number greater than 2                       
                                                 if                                     (n >                                     2                                     ):                       
                                                 count                                     +                                     =                                     1                                     ;                       
           
                                                 return                                     (count);                       
           
                         # A function to print the                       
                         # first n numbers that are                       
                         # k-almost primes.                       
                         def                                     printKAlmostPrimes(k, n):                       
                                                 i                                     =                                     1                                     ;                       
                                                 num                                     =                                     2                       
                                                 while                                     (i <                                     =                                     n):                       
                                   
                                                 # Print this number if                       
                                                 # it is k-prime                       
                                                 if                                     (countPrimeFactors(num)                                     =                                     =                                     k):                       
                                                 print                                     (num, end                                     =                                     "");                       
                                                 print                                     (                                     " "                                     , end                                     =                                     "");                       
           
                                                 # Increment count of                       
                                                 # k-primes printed                       
                                                 # so far                       
                                                 i                                     +                                     =                                     1                                     ;                       
                                                 num                                     +                                     =                                     1                                     ;                       
                                                 return                                     ;                       
           
                         # Driver Code                       
                         n                                     =                                     10                                     ;                       
                         k                                     =                                     2                                     ;                       
                         print                                     (                                     "First n k-almost prime numbers:"                                     );                       
                         printKAlmostPrimes(k, n);                       
           
                         # This code is contributed by mits                       

C#

                         // C# Program to print first n                       
                         // numbers that are k-primes                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                                                 // A function to count all prime                       
                                                 // factors of a given number                       
                                                 static                                     int                                     countPrimeFactors(                                     int                                     n)                       
                                                 {                       
                                                 int                                     count = 0;                       
           
                                                 // Count the number of 2s that divide n                       
                                                 while                                     (n % 2 == 0)                       
                                                 {                       
                                                 n = n / 2;                       
                                                 count++;                       
                                                 }                       
           
                                                 // n must be odd at this point. So we                       
                                                 // can skip one element (Note i = i +2)                       
                                                 for                                     (                                     int                                     i = 3; i <= Math.Sqrt(n);                       
                                                 i = i + 2)                       
                                                 {                       
           
                                                 // While i divides n, count i and                       
                                                 // divide n                       
                                                 while                                     (n % i == 0)                       
                                                 {                       
                                                 n = n / i;                       
                                                 count++;                       
                                                 }                       
                                                 }                       
           
                                                 // This condition is to handle                       
                                                 // the case when n is a prime                       
                                                 // number greater than 2                       
                                                 if                                     (n > 2)                       
                                                 count++;                       
           
                                                 return                                     (count);                       
                                                 }                       
           
                                                 // A function to print the first n                       
                                                 // numbers that are k-almost primes.                       
                                                 static                                     void                                     printKAlmostPrimes(                                     int                                     k,                                     int                                     n)                       
                                                 {                       
           
                                                 for                                     (                                     int                                     i = 1, num = 2; i <= n; num++)                       
                                                 {                       
                                   
                                                 // Print this number if it is k-prime                       
                                                 if                                     (countPrimeFactors(num) == k)                       
                                                 {                       
                                                 Console.Write(num +                                     " "                                     );                       
           
                                                 // Increment count of k-primes                       
                                                 // printed so far                       
                                                 i++;                       
                                                 }                       
                                                 }                       
           
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 10, k = 2;                       
                                                 Console.WriteLine(                                     "First "                                     + n +                                     " "                       
                                                 + k +                                     "-almost prime numbers : "                                     );                       
           
                                                 printKAlmostPrimes(k, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal.                       

PHP

                         <?php                       
                         // PHP Program to print first                       
                         // n numbers that are k-primes                       
           
                         // A function to count all prime                       
                         // factors of a given number                       
                         function                                     countPrimeFactors(                                     $n                                     )                       
                         {                       
                                                 $count                                     = 0;                       
           
                                                 // Count the number of                       
                                                 // 2s that divide n                       
                                                 while                                     (                                     $n                                     % 2 == 0)                       
                                                 {                       
                                                 $n                                     =                                     $n                                     / 2;                       
                                                 $count                                     ++;                       
                                                 }                       
           
                                                 // n must be odd at this point.                       
                                                 // So we can skip one                       
                                                 // element (Note i = i +2)                       
                                                 for                                     (                                     $i                                     = 3;                                     $i                                     <= sqrt(                                     $n                                     );                                     $i                                     =                                     $i                                     + 2)                       
                                                 {                       
                                   
                                                 // While i divides n,                       
                                                 // count i and divide n                       
                                                 while                                     (                                     $n                                     %                                     $i                                     == 0)                       
                                                 {                       
                                                 $n                                     =                                     $n                                     /                                     $i                                     ;                       
                                                 $count                                     ++;                       
                                                 }                       
                                                 }                       
           
                                                 // This condition is to handle                       
                                                 // the case when n is a                       
                                                 // prime number greater than 2                       
                                                 if                                     (                                     $n                                     > 2)                       
                                                 $count                                     ++;                       
           
                                                 return                                     (                                     $count                                     );                       
                         }                       
           
                         // A function to print the                       
                         // first n numbers that are                       
                         // k-almost primes.                       
                         function                                     printKAlmostPrimes(                                     $k                                     ,                                     $n                                     )                       
                         {                       
                                                 for                                     (                                     $i                                     = 1,                                     $num                                     = 2;                                     $i                                     <=                                     $n                                     ;                                     $num                                     ++)                       
                                                 {                       
                                   
                                                 // Print this number if                       
                                                 // it is k-prime                       
                                                 if                                     (countPrimeFactors(                                     $num                                     ) ==                                     $k                                     )                       
                                                 {                       
                                                 echo                                     (                                     $num                                     );                       
                                                 echo                                     (                                     " "                                     );                       
           
                                                 // Increment count of                       
                                                 // k-primes printed                       
                                                 // so far                       
                                                 $i                                     ++;                       
                                                 }                       
                                                 }                       
                                                 return                                     ;                       
                         }                       
           
                                                 // Driver Code                       
                                                 $n                                     = 10;                       
                                                 $k                                     = 2;                       
                                                 echo                                     "First $n $k-almost prime numbers:"                                     ;                       
                                                 printKAlmostPrimes(                                     $k                                     ,                                     $n                                     );                       
           
                         // This code is contributed by nitin mittal.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to print first n numbers that                       
                         // are k-primes                       
           
                                                 // A function to count all prime factors                       
                                                 // of a given number                       
                                                 function                                     countPrimeFactors(n)                       
                                                 {                       
                                   
                                                 let count = 0;                       
                                   
                                                 // Count the number of 2s that divide n                       
                                                 while                                     (n % 2 == 0) {                       
                                   
                                                 n = n / 2;                       
                                                 count++;                       
                                                 }                       
                                   
                                                 // n must be odd at this point. So we                       
                                                 // can skip one element (Note i = i +2)                       
                                                 for                                     (let i = 3; i <= Math.sqrt(n);                       
                                                 i = i + 2) {                       
                                   
                                                 // While i divides n, count i and                       
                                                 // divide n                       
                                                 while                                     (n % i == 0) {                       
                                   
                                                 n = n / i;                       
                                                 count++;                       
                                                 }                       
                                                 }                       
                                   
                                                 // This condition is to handle the case                       
                                                 // when n is a prime number greater                       
                                                 // than 2                       
                                                 if                                     (n > 2)                       
                                                 count++;                       
                                   
                                                 return                                     (count);                       
                                                 }                       
                                   
                                                 // A function to print the first n numbers                       
                                                 // that are k-almost primes.                       
                                                 function                                     printKAlmostPrimes(k, n)                       
                                                 {                       
                                   
                                                 for                                     (let i = 1, num = 2; i <= n; num++) {                       
                                   
                                                 // Print this number if it is k-prime                       
                                                 if                                     (countPrimeFactors(num) == k) {                       
                                   
                                                 document.write(num +                                     " "                                     );                       
                                   
                                                 // Increment count of k-primes                       
                                                 // printed so far                       
                                                 i++;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     ;                       
                                                 }                       
           
                         // Driver Code                       
                                   
                                                 let n = 10, k = 2;                       
                                                 document.write(                                     "First "                                     + n +                                     " "                       
                                                 + k +                                     "-almost prime numbers : "                                     +                                     "<br/>"                                     );                       
                                   
                                                 printKAlmostPrimes(k, n);                       
                                   
                         </script>                       

输出

First 10 2-almost prime numbers : 4 6 9 10 14 15 21 22 25 26

参考资料： https://en.wikipedia.org/wiki/Almost_prime

本文由 拉希特·贝尔瓦里亚 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章