对于一个给定的数N，我如何找到x，S的乘积（x和x的因子数）= N？

Question

找到一些因素，我使用功能void primeFactors(int n)

# include <stdio.h> 
# include <math.h> 
# include <iostream> 
# include <map> 

using namespace std; 
// A function to print all prime factors of a given number n 
map<int,int> m; 
void primeFactors(int n) 
{ 
    // Print the number of 2s that divide n 
    while (n%2 == 0) 
    { 
     printf("%d ", 2); 
     m[2] += 1; 
     n = n/2; 
    } 

    // 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, print i and divide n 
     while (n%i == 0) 
     { 
      int k = i; 
      printf("%d ", i); 
      m[k] += 1; 
      n = n/i; 
     } 
    } 

    // This condition is to handle the case whien n is a prime number 
    // greater than 2 
    if (n > 2) 
     m[n] += 1; 
     printf ("%d ", n); 


    cout << endl; 
} 

/* Driver program to test above function */ 
int main() 
{ 
    int n = 72; 
    primeFactors(n); 
    map<int,int>::iterator it; 
    int to = 1; 
    for(it = m.begin(); it != m.end(); ++it){ 
     cout << it->first << " appeared " << it->second << " times "<< endl; 
     to *= (it->second+1); 
    } 
    cout << to << " total facts" << endl; 
    return 0; 
} 

您可以点击此处查看。 Test case n = 72。 http://ideone.com/kaabO0

如何使用上述算法解决上述问题。 （可以优化更多吗？）。我也必须考虑大数字。

我想要做什么.. 就拿例如，对于N = 864，我们发现X = 72（72 * 12（没有的因素。））= 864）

Answer 1

有一个质因式分解算法对于大数字，但实际上并不常用于编程比赛。
我解释了3种方法，你可以用这个算法来实现。
如果你执行，我建议解决this problem。
注意：在这个答案中，我使用整数Q作为查询的数量。每次查询

O（Q *的sqrt（N））解决方案
你的算法的时间复杂度为O(n^0.5)。
但是你正在用int（32位）实现，所以你可以使用长整型。
这里是我的实现：http://ideone.com/gkGkkP

O（开方（MAXN）*日志（LOG（MAXN））+ Q *的sqrt（MAXN）/日志（MAXN））算法
您可以减少循环的次数因为复合数字对于整数i不是必须的。
所以，你只能在循环中使用素数。

算法：

1. 计算所有质数< =开方（N）与埃拉托色尼的筛子。时间复杂度为O（sqrt（maxn）* log（log（maxn）））。
2. 在查询中，我为循环（我< = sqrt（n）和我是素数）。有效整数i约为sqrt（n）/ log（n），其素数定理为每个查询的时间复杂度为O（sqrt（n）/ log（n））。

更高效的算法
有在世界上更有效的算法，但它不是在编程竞赛经常使用。
如果您在互联网或维基百科上选中“整数因子分解算法”，您可以找到Pollard's-rho或General number字段筛选等算法。

Answer 2

我最好的选择是在表演时不会因为特殊的演习而过度。

的Erathostenes'钛硅分子筛 - 在的下面复杂度为O（N *日志（日志（N））） - 由于内j循环从i*i代替i开始。

#include <vector> 
using std::vector; 

void erathostenes_sieve(size_t upToN, vector<size_t>& primes) { 
    primes.clear(); 
    vector<bool> bitset(upToN+1, true); // if the bitset[i] is true, the i is prime 
    bitset[0]=bitset[1]=0; 

    // if i is 2, will jump to 3, otherwise will jump on odd numbers only 
    for(size_t i=2; i<=upToN; i+=((i&1) ? 2 : 1)) { 
    if(bitset[i]) { // i is prime 
     primes.push_back(i); 
     // it is enough to start the next cycle from i*i, because all the 
     // other primality tests below it are already performed: 
     // e.g: 
     // - i*(i-1) was surely marked non-prime when we considered multiples of 2 
     // - i*(i-2) was tested at (i-2) if (i-2) was prime or earlier (if non-prime) 
     for(size_t j=i*i; j<upToN; j+=i) { 
     bitset[j]=false; // all multiples of the prime with value of i 
          // are marked non-prime, using **addition only** 
     } 
    } 
    } 
} 

---

现在保基础上，primes（在组排序矢量）。在此之前，让我们来看看sqrt的神话价格昂贵，但大量的乘法不是。

首先，让我们注意到，sqrt is not that expensive anymore：旧的CPU-ES上（86/32B），它使用的是贵一倍的分裂（和modulo操作为师），在新架构的CPU成本是平等的。由于因式分解一次又一次地都是大约%操作，所以人们现在仍然可以考虑sqrt（例如，如果和当使用它时节省CPU时间）。

例如，考虑用于N=65537下面的代码（其是6553个素数）假定primes具有10000 entries

size_t limit=std::sqrt(N); 
size_t largestPrimeGoodForN=std::distance(
    primes.begin(), 
    std::upper_limit(primes.begin(), primes.end(), limit) // binary search 
); 
// go descendingly from limit!!! 
for(int i=largestPrimeGoodForN; i>=0; i--) { 
    // factorisation loop 
} 

我们有：

• 1 SQRT（等于1 modulo） ，
• 1在10000条目中搜索 - 最多14个步骤，每个包含1个比较，1个右移2分频和1个递增/递减 - s我们假设一个等于14-20次乘法的成本（如果有的话）
• 由于std::distance的差异。

因此，最大的成本 - 1格和20毫秒？我很慷慨。

在另一边：

for(int i=0; primes[i]*primes[i]<N; i++) { 
    // factorisation code 
} 

看起来简单得多，但是作为N=65537是素数，我们将通过所有的周期可达i=64（我们会在第一黄金造成循环打破） - 总共65次乘法。
用一个更高的素数尝试一下，我保证1 sqrt + 1的二进制搜索的代价更好地利用了CPU周期比所有乘法中的更简单形式的周期吹捧为更好的性能解决方案

---

所以，回到因式分解代码：

#include <algorithm> 
#include <math> 
#include <unordered_map> 
void factor(size_t N, std::unordered_map<size_t, size_t>& factorsWithMultiplicity) { 
     factorsWithMultiplicity.clear(); 

    while(!(N & 1)) { // while N is even, cheaper test than a '% 2' 
    factorsWithMultiplicity[2]++; 
    N = N >> 1; // div by 2 of an unsigned number, cheaper than the actual /2 
    } 
    // now that we know N is even, we start using the primes from the sieve 
    size_t limit=std::sqrt(N); // sqrt is no longer *that* expensive, 

    vector<size_t> primes; 
    // fill the primes up to the limit. Let's be generous, add 1 to it 
    erathostenes_sieve(limit+1, primes); 
    // we know that the largest prime worth checking is 
    // the last element of the primes. 
    for(
    size_t largestPrimeIndexGoodForN=primes.size()-1; 
    largestPrimeIndexGoodForN<primes.size(); // size_t is unsigned, so after zero will underflow 
    // we'll handle the cycle index inside 
    ) { 
    bool wasFactor=false; 
    size_t factorToTest=primes[largestPrimeIndexGoodForN]; 
    while(!(N % factorToTest)) { 
     wasFactor=true;// found one 
     factorsWithMultiplicity[factorToTest]++; 
     N /= factorToTest; 
    } 
    if(1==N) { // done 
     break; 
    } 
    if(wasFactor) { // time to resynchronize the index 
     limit=std::sqrt(N); 
     largestPrimeIndexGoodForN=std::distance(
      primes.begin(), 
      std::upper_bound(primes.begin(), primes.end(), limit) 
     ); 
    } 
    else { // no luck this time 
     largestPrimeIndexGoodForN--; 
    } 
    } // done the factoring cycle 
    if(N>1) { // N was prime to begin with 
    factorsWithMultiplicity[N]++; 
    } 
} 

Answer 3

好吧，我会告诉你的代码。

# include <stdio.h> 
# include <iostream> 
# include <map> 
using namespace std; 
const long MAX_NUM = 2000000; 
long prime[MAX_NUM] = {0}, primeCount = 0; 
bool isNotPrime[MAX_NUM] = {1, 1}; // yes. can be improve, but it is useless when sieveOfEratosthenes is end 
void sieveOfEratosthenes() { 
    //@see https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 
    for (long i = 2; i < MAX_NUM; i++) { // it must be i++ 
     if (!isNotPrime[i]) //if it is prime,put it into prime[] 
      prime[primeCount++] = i; 
     for (long j = 0; j < primeCount && i * prime[j] < MAX_NUM; j++) { /*foreach prime[]*/ 
//   if(i * prime[j] >= MAX_NUM){ // if large than MAX_NUM break 
//    break; 
//   } 
      isNotPrime[i * prime[j]] = 1; // set i * prime[j] not a prime.as you see, i * prime[j] 
      if (!(i % prime[j])) //if this prime the min factor of i,than break. 
           // and it is the answer why not i+=((i & 1) ? 2 : 1). 
           // hint : when we judge 2,prime[]={2},we set 2*2=4 not prime 
           //  when we judge 3,prime[]={2,3},we set 3*2=6 3*3=9 not prime 
           //  when we judge 4,prime[]={2,3},we set 4*2=8 not prime (why not set 4*3=12?) 
           //  when we judge 5,prime[]={2,3,5},we set 5*2=10 5*3=15 5*5=25 not prime 
           //  when we judge 6,prime[]={2,3,5},we set 6*2=12 not prime,than we can stop 
           // why not put 6*3=18 6*5=30 not prime? 18=9*2 30=15*2. 
           // this code can make each num be set only once,I hope it can help you to understand 
           // this is difficult to understand but very useful. 
       break; 
     } 
    } 
} 
void primeFactors(long n) 
{ 
    map<int,int> m; 
    map<int,int>::iterator it; 
    for (int i = 0; prime[i] <= n; i++) // we test all prime small than n , like 2 3 5 7... it musut be i++ 
    { 
     while (n%prime[i] == 0) 
     { 
      cout<<prime[i]<<" "; 
      m[prime[i]] += 1; 
      n = n/prime[i]; 
     } 
    } 
    cout<<endl; 
    int to = 1; 
    for(it = m.begin(); it != m.end(); ++it){ 
     cout << it->first << " appeared " << it->second << " times "<< endl; 
     to *= (it->second+1); 
    } 
    cout << to << " total facts" << endl; 

} 
int main() 
{ 
    //first init for calculate all prime numbers,for example we define MAX_NUM = 2000000 
    // the result of prime[] should be stored, you primeFactors will use it 
    sieveOfEratosthenes(); 
    //second loop for i (i*i <= n and i is a prime number). n<=MAX_NUM 
    int n = 72; 
    primeFactors(n); 
    n = 864; 
    primeFactors(n); 
    return 0; 
}