对多个查询使用筛O（logn）进行素因子分解-yiteyi-C++库

我们可以计算一个数的素因式分解 “n” 在里面 O（sqrt（n）） 如前所述在这里但是当我们需要回答关于素数分解的多个查询时，O（sqrt n）方法会超时。在这篇文章中，我们研究了一种利用O（n）空间和 O（对数n） 允许预计算的时间复杂度。

null

先决条件： 埃拉托斯坦筛 , n之前数的最小素数因子 .

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

关键概念： 我们的想法是存储每个数字的最小素因子（SPF）。然后，通过递归地将给定的数与其最小的素数因子相除，直到它变成1，来计算给定数的素数因子分解。

为了计算每个数的最小素因子，我们将使用埃拉托斯坦筛 .在原始筛选中，每次我们将一个数字标记为非素数时，我们都会存储该数字对应的最小素数因子（参见这文章（以便更好地理解）。

现在，在我们为每个数字预先计算了最小的素因子之后，我们将把我们的数字n（其素因子分解将被计算）除以它相应的最小素因子，直到n变成1。

Pseudo Code for prime factorization assumingSPFs are computed :PrimeFactors[] // To store resulti = 0  // Index in PrimeFactorswhile n != 1 :    // SPF : smallest prime factor    PrimeFactors[i] = SPF[n]        i++     n = n / SPF[n]

下面给出了上述方法的实现：

C++

                         // C++ program to find prime factorization of a                       
                         // number n in O(Log n) time with precomputation                       
                         // allowed.                       
                         #include "bits/stdc++.h"                       
                         using                                     namespace                                     std;                       
           
                         #define MAXN   100001                       
           
                         // stores smallest prime factor for every number                       
                         int                                     spf[MAXN];                       
           
                         // Calculating SPF (Smallest Prime Factor) for every                       
                         // number till MAXN.                       
                         // Time Complexity : O(nloglogn)                       
                         void                                     sieve()                       
                         {                       
                                                 spf[1] = 1;                       
                                                 for                                     (                                     int                                     i=2; i<MAXN; i++)                       
           
                                                 // marking smallest prime factor for every                       
                                                 // number to be itself.                       
                                                 spf[i] = i;                       
           
                                                 // separately marking spf for every even                       
                                                 // number as 2                       
                                                 for                                     (                                     int                                     i=4; i<MAXN; i+=2)                       
                                                 spf[i] = 2;                       
           
                                                 for                                     (                                     int                                     i=3; i*i<MAXN; i++)                       
                                                 {                       
                                                 // checking if i is prime                       
                                                 if                                     (spf[i] == i)                       
                                                 {                       
                                                 // marking SPF for all numbers divisible by i                       
                                                 for                                     (                                     int                                     j=i*i; j<MAXN; j+=i)                       
           
                                                 // marking spf[j] if it is not                       
                                                 // previously marked                       
                                                 if                                     (spf[j]==j)                       
                                                 spf[j] = i;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // A O(log n) function returning primefactorization                       
                         // by dividing by smallest prime factor at every step                       
                         vector<                                     int                                     > getFactorization(                                     int                                     x)                       
                         {                       
                                                 vector<                                     int                                     > ret;                       
                                                 while                                     (x != 1)                       
                                                 {                       
                                                 ret.push_back(spf[x]);                       
                                                 x = x / spf[x];                       
                                                 }                       
                                                 return                                     ret;                       
                         }                       
           
                         // driver program for above function                       
                         int                                     main(                                     int                                     argc,                                     char                                     const                                     *argv[])                       
                         {                       
                                                 // precalculating Smallest Prime Factor                       
                                                 sieve();                       
                                                 int                                     x = 12246;                       
                                                 cout <<                                     "prime factorization for "                                     << x <<                                     " : "                                     ;                       
           
                                                 // calling getFactorization function                       
                                                 vector <                                     int                                     > p = getFactorization(x);                       
           
                                                 for                                     (                                     int                                     i=0; i<p.size(); i++)                       
                                                 cout << p[i] <<                                     " "                                     ;                       
                                                 cout << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find prime factorization of a                       
                         // number n in O(Log n) time with precomputation                       
                         // allowed.                       
           
                         import                                     java.util.Vector;                       
           
                         class                                     Test                       
                         {                       
                                                 static                                     final                                     int                                     MAXN =                                     100001                                     ;                       
                                   
                                                 // stores smallest prime factor for every number                       
                                                 static                                     int                                     spf[] =                                     new                                     int                                     [MAXN];                       
                                   
                                                 // Calculating SPF (Smallest Prime Factor) for every                       
                                                 // number till MAXN.                       
                                                 // Time Complexity : O(nloglogn)                       
                                                 static                                     void                                     sieve()                       
                                                 {                       
                                                 spf[                                     1                                     ] =                                     1                                     ;                       
                                                 for                                     (                                     int                                     i=                                     2                                     ; i<MAXN; i++)                       
                                   
                                                 // marking smallest prime factor for every                       
                                                 // number to be itself.                       
                                                 spf[i] = i;                       
                                   
                                                 // separately marking spf for every even                       
                                                 // number as 2                       
                                                 for                                     (                                     int                                     i=                                     4                                     ; i<MAXN; i+=                                     2                                     )                       
                                                 spf[i] =                                     2                                     ;                       
                                   
                                                 for                                     (                                     int                                     i=                                     3                                     ; i*i<MAXN; i++)                       
                                                 {                       
                                                 // checking if i is prime                       
                                                 if                                     (spf[i] == i)                       
                                                 {                       
                                                 // marking SPF for all numbers divisible by i                       
                                                 for                                     (                                     int                                     j=i*i; j<MAXN; j+=i)                       
                                   
                                                 // marking spf[j] if it is not                       
                                                 // previously marked                       
                                                 if                                     (spf[j]==j)                       
                                                 spf[j] = i;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // A O(log n) function returning primefactorization                       
                                                 // by dividing by smallest prime factor at every step                       
                                                 static                                     Vector<Integer> getFactorization(                                     int                                     x)                       
                                                 {                       
                                                 Vector<Integer> ret =                                     new                                     Vector<>();                       
                                                 while                                     (x !=                                     1                                     )                       
                                                 {                       
                                                 ret.add(spf[x]);                       
                                                 x = x / spf[x];                       
                                                 }                       
                                                 return                                     ret;                       
                                                 }                       
                                   
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 // precalculating Smallest Prime Factor                       
                                                 sieve();                       
                                                 int                                     x =                                     12246                                     ;                       
                                                 System.out.print(                                     "prime factorization for "                                     + x +                                     " : "                                     );                       
                                   
                                                 // calling getFactorization function                       
                                                 Vector <Integer> p = getFactorization(x);                       
                                   
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<p.size(); i++)                       
                                                 System.out.print(p.get(i) +                                     " "                                     );                       
                                                 System.out.println();                       
                                                 }                       
                         }                       

Python3

                         # Python3 program to find prime factorization                       
                         # of a number n in O(Log n) time with                       
                         # precomputation allowed.                       
                         import                                     math as mt                       
           
                         MAXN                                     =                                     100001                       
           
                         # stores smallest prime factor for                       
                         # every number                       
                         spf                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (MAXN)]                       
           
                         # Calculating SPF (Smallest Prime Factor)                       
                         # for every number till MAXN.                       
                         # Time Complexity : O(nloglogn)                       
                         def                                     sieve():                       
                                                 spf[                                     1                                     ]                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (                                     2                                     , MAXN):                       
                                   
                                                 # marking smallest prime factor                       
                                                 # for every number to be itself.                       
                                                 spf[i]                                     =                                     i                       
           
                                                 # separately marking spf for                       
                                                 # every even number as 2                       
                                                 for                                     i                                     in                                     range                                     (                                     4                                     , MAXN,                                     2                                     ):                       
                                                 spf[i]                                     =                                     2                       
           
                                                 for                                     i                                     in                                     range                                     (                                     3                                     , mt.ceil(mt.sqrt(MAXN))):                       
                                   
                                                 # checking if i is prime                       
                                                 if                                     (spf[i]                                     =                                     =                                     i):                       
                                   
                                                 # marking SPF for all numbers                       
                                                 # divisible by i                       
                                                 for                                     j                                     in                                     range                                     (i                                     *                                     i, MAXN, i):                       
                                   
                                                 # marking spf[j] if it is                       
                                                 # not previously marked                       
                                                 if                                     (spf[j]                                     =                                     =                                     j):                       
                                                 spf[j]                                     =                                     i                       
           
                         # A O(log n) function returning prime                       
                         # factorization by dividing by smallest                       
                         # prime factor at every step                       
                         def                                     getFactorization(x):                       
                                                 ret                                     =                                     list                                     ()                       
                                                 while                                     (x !                                     =                                     1                                     ):                       
                                                 ret.append(spf[x])                       
                                                 x                                     =                                     x                                     /                                     /                                     spf[x]                       
           
                                                 return                                     ret                       
           
                         # Driver code                       
           
                         # precalculating Smallest Prime Factor                       
                         sieve()                       
                         x                                     =                                     12246                       
                         print                                     (                                     "prime factorization for"                                     , x,                                     ": "                                     ,                       
                                                 end                                     =                                     "")                       
           
                         # calling getFactorization function                       
                         p                                     =                                     getFactorization(x)                       
           
                         for                                     i                                     in                                     range                                     (                                     len                                     (p)):                       
                                                 print                                     (p[i], end                                     =                                     " "                                     )                       
           
                         # This code is contributed                       
                         # by Mohit kumar 29                       

C#

                         // C# program to find prime factorization of a                       
                         // number n in O(Log n) time with precomputation                       
                         // allowed.                       
                         using                                     System;                       
                         using                                     System.Collections;                       
           
                         class                                     GFG                       
                         {                       
                                                 static                                     int                                     MAXN = 100001;                       
                                   
                                                 // stores smallest prime factor for every number                       
                                                 static                                     int                                     [] spf =                                     new                                     int                                     [MAXN];                       
                                   
                                                 // Calculating SPF (Smallest Prime Factor) for every                       
                                                 // number till MAXN.                       
                                                 // Time Complexity : O(nloglogn)                       
                                                 static                                     void                                     sieve()                       
                                                 {                       
                                                 spf[1] = 1;                       
                                                 for                                     (                                     int                                     i = 2; i < MAXN; i++)                       
                                   
                                                 // marking smallest prime factor for every                       
                                                 // number to be itself.                       
                                                 spf[i] = i;                       
                                   
                                                 // separately marking spf for every even                       
                                                 // number as 2                       
                                                 for                                     (                                     int                                     i = 4; i < MAXN; i += 2)                       
                                                 spf[i] = 2;                       
                                   
                                                 for                                     (                                     int                                     i = 3; i * i < MAXN; i++)                       
                                                 {                       
                                                 // checking if i is prime                       
                                                 if                                     (spf[i] == i)                       
                                                 {                       
                                                 // marking SPF for all numbers divisible by i                       
                                                 for                                     (                                     int                                     j = i * i; j < MAXN; j += i)                       
                                   
                                                 // marking spf[j] if it is not                       
                                                 // previously marked                       
                                                 if                                     (spf[j] == j)                       
                                                 spf[j] = i;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // A O(log n) function returning primefactorization                       
                                                 // by dividing by smallest prime factor at every step                       
                                                 static                                     ArrayList getFactorization(                                     int                                     x)                       
                                                 {                       
                                                 ArrayList ret =                                     new                                     ArrayList();                       
                                                 while                                     (x != 1)                       
                                                 {                       
                                                 ret.Add(spf[x]);                       
                                                 x = x / spf[x];                       
                                                 }                       
                                                 return                                     ret;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 // precalculating Smallest Prime Factor                       
                                                 sieve();                       
                                                 int                                     x = 12246;                       
                                                 Console.Write(                                     "prime factorization for "                                     + x +                                     " : "                                     );                       
                                   
                                                 // calling getFactorization function                       
                                                 ArrayList p = getFactorization(x);                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < p.Count; i++)                       
                                                 Console.Write(p[i] +                                     " "                                     );                       
                                                 Console.WriteLine(                                     ""                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by mits                       

PHP

                         <?php                       
                         // PHP program to find prime factorization                       
                         // of a number n in O(Log n) time with                       
                         // precomputation allowed.                       
           
                         $MAXN                                     = 19999;                       
           
                         // stores smallest prime factor for                       
                         // every number                       
                         $spf                                     =                                     array_fill                                     (0,                                     $MAXN                                     , 0);                       
           
                         // Calculating SPF (Smallest Prime Factor)                       
                         // for every number till MAXN.                       
                         // Time Complexity : O(nloglogn)                       
                         function                                     sieve()                       
                         {                       
                                                 global                                     $MAXN                                     ,                                     $spf                                     ;                       
                                                 $spf                                     [1] = 1;                       
                                                 for                                     (                                     $i                                     = 2;                                     $i                                     <                                     $MAXN                                     ;                                     $i                                     ++)                       
           
                                                 // marking smallest prime factor                       
                                                 // for every number to be itself.                       
                                                 $spf                                     [                                     $i                                     ] =                                     $i                                     ;                       
           
                                                 // separately marking spf for every                       
                                                 // even number as 2                       
                                                 for                                     (                                     $i                                     = 4;                                     $i                                     <                                     $MAXN                                     ;                                     $i                                     += 2)                       
                                                 $spf                                     [                                     $i                                     ] = 2;                       
           
                                                 for                                     (                                     $i                                     = 3;                                     $i                                     *                                     $i                                     <                                     $MAXN                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // checking if i is prime                       
                                                 if                                     (                                     $spf                                     [                                     $i                                     ] ==                                     $i                                     )                       
                                                 {                       
                                                 // marking SPF for all numbers                       
                                                 // divisible by i                       
                                                 for                                     (                                     $j                                     =                                     $i                                     *                                     $i                                     ;                                     $j                                     <                                     $MAXN                                     ;                                     $j                                     +=                                     $i                                     )                       
           
                                                 // marking spf[j] if it is not                       
                                                 // previously marked                       
                                                 if                                     (                                     $spf                                     [                                     $j                                     ] ==                                     $j                                     )                       
                                                 $spf                                     [                                     $j                                     ] =                                     $i                                     ;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // A O(log n) function returning primefactorization                       
                         // by dividing by smallest prime factor at every step                       
                         function                                     getFactorization(                                     $x                                     )                       
                         {                       
                                                 global                                     $spf                                     ;                       
                                                 $ret                                     =                                     array                                     ();                       
                                                 while                                     (                                     $x                                     != 1)                       
                                                 {                       
                                                 array_push                                     (                                     $ret                                     ,                                     $spf                                     [                                     $x                                     ]);                       
                                                 if                                     (                                     $spf                                     [                                     $x                                     ])                       
                                                 $x                                     = (int)(                                     $x                                     /                                     $spf                                     [                                     $x                                     ]);                       
                                                 }                       
                                                 return                                     $ret                                     ;                       
                         }                       
           
                         // Driver Code                       
           
                         // precalculating Smallest                       
                         // Prime Factor                       
                         sieve();                       
                         $x                                     = 12246;                       
                         echo                                     "prime factorization for "                                     .                       
                                                 $x                                     .                                     " : "                                     ;                       
           
                         // calling getFactorization function                       
                         $p                                     = getFactorization(                                     $x                                     );                       
           
                         for                                     (                                     $i                                     = 0;                                     $i                                     <                                     count                                     (                                     $p                                     );                                     $i                                     ++)                       
                                                 echo                                     $p                                     [                                     $i                                     ] .                                     " "                                     ;                       
           
                         // This code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
                         // Javascript program to find prime factorization of a                       
                         // number n in O(Log n) time with precomputation                       
                         // allowed.                       
                                   
                                                 let MAXN = 100001;                       
                                                 // stores smallest prime factor for every number                       
                                                 let spf=                                     new                                     Array(MAXN);                       
                                   
                                                 // Calculating SPF (Smallest Prime Factor) for every                       
                                                 // number till MAXN.                       
                                                 // Time Complexity : O(nloglogn)                       
                                                 function                                     sieve()                       
                                                 {                       
                                                 spf[1] = 1;                       
                                                 for                                     (let i=2; i<MAXN; i++)                       
                                   
                                                 // marking smallest prime factor for every                       
                                                 // number to be itself.                       
                                                 spf[i] = i;                       
                                   
                                                 // separately marking spf for every even                       
                                                 // number as 2                       
                                                 for                                     (let i=4; i<MAXN; i+=2)                       
                                                 spf[i] = 2;                       
                                   
                                                 for                                     (let i=3; i*i<MAXN; i++)                       
                                                 {                       
                                                 // checking if i is prime                       
                                                 if                                     (spf[i] == i)                       
                                                 {                       
                                                 // marking SPF for all numbers divisible by i                       
                                                 for                                     (let j=i*i; j<MAXN; j+=i)                       
                                   
                                                 // marking spf[j] if it is not                       
                                                 // previously marked                       
                                                 if                                     (spf[j]==j)                       
                                                 spf[j] = i;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // A O(log n) function returning primefactorization                       
                                                 // by dividing by smallest prime factor at every step                       
                                                 function                                     getFactorization(x)                       
                                                 {                       
                                                 let ret =[];                       
                                                 while                                     (x != 1)                       
                                                 {                       
                                                 ret.push(spf[x]);                       
                                                 x = Math.floor(x / spf[x]);                       
                                                 }                       
                                                 return                                     ret;                       
                                                 }                       
                                   
                                                 // Driver method                       
                                   
                                                 // precalculating Smallest Prime Factor                       
                                                 sieve();                       
                                                 let x = 12246;                       
                                                 document.write(                                     "prime factorization for "                                     + x +                                     " : "                                     );                       
                                                 // calling getFactorization function                       
                                                 let  p = getFactorization(x);                       
                                                 for                                     (let i=0; i<p.length; i++)                       
                                                 document.write(p[i] +                                     " "                                     );                       
                                                 document.write(                                     "<br>"                                     );                       
                                   
                                   
           
                         // This code is contributed by unknown2108                       
                         </script>                       

输出：

prime factorization for 12246 : 2 3 13 157

注：以上代码适用于n，最高可达10^7。除此之外，我们还将面临内存问题。

时间复杂性： 最小素因子的预计算是在O（n logn logn）中使用筛子完成的。而在计算步骤中，我们每次都将这个数除以最小的素数，直到它变成1。所以，让我们考虑一个最坏的情况，每次SPF为2。因此将有日志n分割步骤。因此，我们可以说，我们的时间复杂性将是 O（对数n） 在最坏的情况下。

本文由 尼蒂什·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章