n之前数的最小素数因子-yiteyi-C++库

给定一个数字 N 打印 最小素因子 在从1到n的所有数字中，整数n的最小素数因子是除以该数字的最小素数。所有偶数中的最小素数因子是2。素数是它自己的最小素数因子（以及它自己的最大素数因子）。注：我们需要打印1对1。 例子：

null

Input : 6Output : Least Prime factor of 1: 1         Least Prime factor of 2: 2         Least Prime factor of 3: 3         Least Prime factor of 4: 2         Least Prime factor of 5: 5         Least Prime factor of 6: 2

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

我们可以使用埃拉托斯坦筛解决上述问题。

创建一个从2到n的连续整数列表：（2，3，4，…，n）。
首先，让我等于2，最小的素数。
通过以i的增量从2i数到n来枚举i的倍数，并将它们标记为素数因子最少的i（如果尚未标记）。也将i标记为i的最小素数因子（i本身是素数）。
在列表中找到第一个大于i且未标记的数字。如果没有这样的数字，停下来。否则，让我现在等于这个新数字（它是下一个素数），并从步骤3重复。

下面是算法的实现，其中least_prime[]保存对应于相应索引的最小素数因子的值。

C++

                         // C++ program to print the least prime factors                       
                         // of numbers less than or equal to                       
                         // n using modified Sieve of Eratosthenes                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         void                                     leastPrimeFactor(                                     int                                     n)                       
                         {                       
                                                 // Create a vector to store least primes.                       
                                                 // Initialize all entries as 0.                       
                                                 vector<                                     int                                     > least_prime(n+1, 0);                       
           
                                                 // We need to print 1 for 1.                       
                                                 least_prime[1] = 1;                       
           
                                                 for                                     (                                     int                                     i = 2; i <= n; i++)                       
                                                 {                       
                                                 // least_prime[i] == 0                       
                                                 // means it i is prime                       
                                                 if                                     (least_prime[i] == 0)                       
                                                 {                       
                                                 // marking the prime number                       
                                                 // as its own lpf                       
                                                 least_prime[i] = i;                       
           
                                                 // mark it as a divisor for all its                       
                                                 // multiples if not already marked                       
                                                 for                                     (                                     int                                     j = i*i; j <= n; j += i)                       
                                                 if                                     (least_prime[j] == 0)                       
                                                 least_prime[j] = i;                       
                                                 }                       
                                                 }                       
           
                                                 // print least prime factor of                       
                                                 // of numbers till n                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 cout <<                                     "Least Prime factor of "                       
                                                 << i <<                                     ": "                                     << least_prime[i] <<                                     ""                                     ;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 10;                       
                                                 leastPrimeFactor(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print the least prime factors                       
                         // of numbers less than or equal to                       
                         // n using modified Sieve of Eratosthenes                       
           
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
                                                 public                                     static                                     void                                     leastPrimeFactor(                                     int                                     n)                       
                                                 {                       
                                   
                                                 // Create a vector to store least primes.                       
                                                 // Initialize all entries as 0.                       
                                                 int                                     [] least_prime =                                     new                                     int                                     [n+                                     1                                     ];                       
           
                                                 // We need to print 1 for 1.                       
                                                 least_prime[                                     1                                     ] =                                     1                                     ;                       
           
                                                 for                                     (                                     int                                     i =                                     2                                     ; i <= n; i++)                       
                                                 {                       
                                   
                                                 // least_prime[i] == 0                       
                                                 // means it i is prime                       
                                                 if                                     (least_prime[i] ==                                     0                                     )                       
                                                 {                       
                                   
                                                 // marking the prime number                       
                                                 // as its own lpf                       
                                                 least_prime[i] = i;                       
           
                                                 // mark it as a divisor for all its                       
                                                 // multiples if not already marked                       
                                                 for                                     (                                     int                                     j = i*i; j <= n; j += i)                       
                                                 if                                     (least_prime[j] ==                                     0                                     )                       
                                                 least_prime[j] = i;                       
                                                 }                       
                                                 }                       
           
                                                 // print least prime factor of                       
                                                 // of numbers till n                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 System.out.println(                                     "Least Prime factor of "                                     +                       
                                                 + i +                                     ": "                                     + least_prime[i]);                       
                                                 }                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     n =                                     10                                     ;                       
                                                 leastPrimeFactor(n);                       
                                                 }                       
                         }                       
           
                         // Code Contributed by Mohit Gupta_OMG <(0_o)>                       

Python 3

                         # Python 3 program to print the                       
                         # least prime factors of numbers                       
                         # less than or equal to n using                       
                         # modified Sieve of Eratosthenes                       
           
                         def                                     leastPrimeFactor(n) :                       
                                   
                                                 # Create a vector to store least primes.                       
                                                 # Initialize all entries as 0.                       
                                                 least_prime                                     =                                     [                                     0                                     ]                                     *                                     (n                                     +                                     1                                     )                       
           
                                                 # We need to print 1 for 1.                       
                                                 least_prime[                                     1                                     ]                                     =                                     1                       
           
                                                 for                                     i                                     in                                     range                                     (                                     2                                     , n                                     +                                     1                                     ) :                       
                                   
                                                 # least_prime[i] == 0                       
                                                 # means it i is prime                       
                                                 if                                     (least_prime[i]                                     =                                     =                                     0                                     ) :                       
                                   
                                                 # marking the prime number                       
                                                 # as its own lpf                       
                                                 least_prime[i]                                     =                                     i                       
           
                                                 # mark it as a divisor for all its                       
                                                 # multiples if not already marked                       
                                                 for                                     j                                     in                                     range                                     (i                                     *                                     i, n                                     +                                     1                                     , i) :                       
                                                 if                                     (least_prime[j]                                     =                                     =                                     0                                     ) :                       
                                                 least_prime[j]                                     =                                     i                       
                                   
                                   
                                                 # print least prime factor                       
                                                 # of numbers till n                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ) :                       
                                                 print                                     (                                     "Least Prime factor of "                       
                                                 ,i ,                                     ": "                                     , least_prime[i] )                       
                                   
           
                         # Driver program                       
           
                         n                                     =                                     10                       
                         leastPrimeFactor(n)                       
           
           
                         # This code is contributed                       
                         # by Nikita Tiwari.                       

C#

                         // C# program to print the least prime factors                       
                         // of numbers less than or equal to                       
                         // n using modified Sieve of Eratosthenes                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 public                                     static                                     void                                     leastPrimeFactor(                                     int                                     n)                       
                                                 {                       
                                                 // Create a vector to store least primes.                       
                                                 // Initialize all entries as 0.                       
                                                 int                                     []least_prime =                                     new                                     int                                     [n+1];                       
           
                                                 // We need to print 1 for 1.                       
                                                 least_prime[1] = 1;                       
           
                                                 for                                     (                                     int                                     i = 2; i <= n; i++)                       
                                                 {                       
                                                 // least_prime[i] == 0                       
                                                 // means it i is prime                       
                                                 if                                     (least_prime[i] == 0)                       
                                                 {                       
                                                 // marking the prime number                       
                                                 // as its own lpf                       
                                                 least_prime[i] = i;                       
           
                                                 // mark it as a divisor for all its                       
                                                 // multiples if not already marked                       
                                                 for                                     (                                     int                                     j = i*i; j <= n; j += i)                       
                                                 if                                     (least_prime[j] == 0)                       
                                                 least_prime[j] = i;                       
                                                 }                       
                                                 }                       
           
                                                 // print least prime factor of                       
                                                 // of numbers till n                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 Console.WriteLine(                                     "Least Prime factor of "                                     +                       
                                                 i +                                     ": "                                     + least_prime[i]);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     n = 10;                       
                                   
                                                 // Function calling                       
                                                 leastPrimeFactor(n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal                       

PHP

                         <?php                       
                         // PHP program to print the                       
                         // least prime factors of                       
                         // numbers less than or equal                       
                         // to n using modified Sieve                       
                         // of Eratosthenes                       
           
                         function                                     leastPrimeFactor(                                     $n                                     )                       
                         {                       
                                                 // Create a vector to                       
                                                 // store least primes.                       
                                                 // Initialize all entries                       
                                                 // as 0.                       
                                                 $least_prime                                     =                                     array                                     (                                     $n                                     + 1);                       
                                   
                                                 for                                     (                                     $i                                     = 0;                       
                                                 $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 $least_prime                                     [                                     $i                                     ] = 0;                       
                                   
                                                 // We need to                       
                                                 // print 1 for 1.                       
                                                 $least_prime                                     [1] = 1;                       
           
                                                 for                                     (                                     $i                                     = 2;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // least_prime[i] == 0                       
                                                 // means it i is prime                       
                                                 if                                     (                                     $least_prime                                     [                                     $i                                     ] == 0)                       
                                                 {                       
                                                 // marking the prime                       
                                                 // number as its own lpf                       
                                                 $least_prime                                     [                                     $i                                     ] =                                     $i                                     ;                       
           
                                                 // mark it as a divisor                       
                                                 // for all its multiples                       
                                                 // if not already marked                       
                                                 for                                     (                                     $j                                     =                                     $i                                     *                                     $i                                     ;                       
                                                 $j                                     <=                                     $n                                     ;                                     $j                                     +=                                     $i                                     )                       
                                                 if                                     (                                     $least_prime                                     [                                     $j                                     ] == 0)                       
                                                 $least_prime                                     [                                     $j                                     ] =                                     $i                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // print least prime                       
                                                 // factor of numbers                       
                                                 // till n                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 echo                                     "Least Prime factor of "                                     .                       
                                                 $i                                     .                                     ": "                                     .                       
                                                 $least_prime                                     [                                     $i                                     ] .                                     ""                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 10;                       
                         leastPrimeFactor(                                     $n                                     );                       
           
                         // This code is contributed                       
                         // by Sam007                       
                         ?>                       

Javascript

                         <script>                       
                         // javascript program to print the least prime factors                       
                         // of numbers less than or equal to                       
                         // n using modified Sieve of Eratosthenes                       
                         function                                     leastPrimeFactor( n)                       
                         {                       
           
                                                 // Create a vector to store least primes.                       
                                                 // Initialize all entries as 0.                       
                                                 let least_prime = Array(n+1).fill(0);                       
           
                                                 // We need to print 1 for 1.                       
                                                 least_prime[1] = 1;                       
           
                                                 for                                     (let i = 2; i <= n; i++)                       
                                                 {                       
           
                                                 // least_prime[i] == 0                       
                                                 // means it i is prime                       
                                                 if                                     (least_prime[i] == 0)                       
                                                 {                       
                                   
                                                 // marking the prime number                       
                                                 // as its own lpf                       
                                                 least_prime[i] = i;                       
           
                                                 // mark it as a divisor for all its                       
                                                 // multiples if not already marked                       
                                                 for                                     (let j = i*i; j <= n; j += i)                       
                                                 if                                     (least_prime[j] == 0)                       
                                                 least_prime[j] = i;                       
                                                 }                       
                                                 }                       
           
                                                 // print least prime factor of                       
                                                 // of numbers till n                       
                                                 for                                     (let i = 1; i <= n; i++)                       
                                                 document.write(                                     "Least Prime factor of "                       
                                                 + i +                                     ": "                                     + least_prime[i] +                                     "<br/>"                                     );                       
                         }                       
           
                         // Driver program to test above function                       
                                                 let n = 10;                       
                                                 leastPrimeFactor(n);                       
                                   
                         // This code is contributed by Rajput-Ji                       
           
                         </script>                       

输出

Least Prime factor of 1: 1Least Prime factor of 2: 2Least Prime factor of 3: 3Least Prime factor of 4: 2Least Prime factor of 5: 5Least Prime factor of 6: 2Least Prime factor of 7: 7Least Prime factor of 8: 2Least Prime factor of 9: 3Least Prime factor of 10: 2

时间复杂性： O（nloglog（n）） 辅助空间： O（n） 参考资料： 1. https://www.geeksforgeeks.org/sieve-of-eratosthenes/ 2. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 3. https://oeis.org/wiki/Least_prime_factor_of_n 练习： 我们可以扩展这个算法吗？或者使用最小素数[]来找到n之前的所有素数因子吗？本文由 阿尤什·坎杜里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章