优化--数<= 10^7的素数分解

Question

我使用带有预先计算素数列表的来计算小于M (M <= 10^7)的所有数的素数因式分解。

我正在使用一组向量对。10的格式如下：

PF[10][0].first = 2 // Base
PF[10][0].second = 1 // Exp
PF[10][1].first = 5
PF[10][1].second = 1

我的方法很好，但太慢了。对于M=10^7，计算我系统上所有数字<=M的PF需要36.841秒。

问题

1. 解决这个问题的最佳方法是哪一种？
2. 对于我的方法，我还能做什么优化呢？

我的代码

#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include "math.h"
#include "stdio.h"
using namespace std;

const int lim=45000;
const int Max=10000000;
char prime[lim];

vector<pair <int,unsigned char> > PF[Max];

void prep()
{
    //Calculation of Prime Numbers
    for(int i=1;i<lim;prime[i++]=1);
    for(int i=2;i*i<lim;i++)
        if(prime[i])
            for(int j=i+i;j<lim;prime[j]=0,j+=i);

    for(int i=2;i<Max;i++) {
        int num=i;
        unsigned char pq=0;
        //Check for powers of 2
        while(num%2==0)  {
            pq++;
            num=num/2;
        } 
        if(pq>0)
            PF[i].push_back( make_pair(2,pq) );
        int pan=num;
        //Loop for all primes j such that j*j<num
        for(int j=3;j*j<=num;j+=2) {
            if(prime[j]) {
                pq=0;
                while(num%j==0) {
                    pq++;
                    num=num/j;
                } 
                if(pq>0)
                    PF[i].push_back( make_pair(j,pq) );
            }
        }
        if(num>1)
            PF[i].push_back( make_pair(num,1) );
    }
}

main()
{
    prep();
}

定时

我的代码

real    0m36.841s
user    0m36.624s
sys     0m0.265s

Igor ostrovsky码

real    0m41.628s
user    0m41.390s
sys     0m0.265s

Answer 1

不久前，为了降低阶乘比，我就这么做了

#include <utility>
#include <vector>

std::vector< std::pair<int, int> > factor_table;
void fill_sieve( int n )
{
    factor_table.resize(n+1);
    for( int i = 1; i <= n; ++i ) {
        if (i & 1)
            factor_table[i] = std::pair<int, int>(i, 1);
        else
            factor_table[i] = std::pair<int, int>(2, i>>1);
    }
    for( int j = 3, j2 = 9; j2 <= n; ) {
        if (factor_table[j].second == 1) {
            int i = j;
            int ij = j2;
            while (ij <= n) {
                factor_table[ij] = std::pair<int, int>(j, i);
                ++i;
                ij += j;
            }
        }
        j2 += (j + 1) << 2;
        j += 2;
    }
}

std::vector<int> factor( int num )
{
    std::vector<int> factors;
    factors.reserve(30);
    do {
        factors.push_back(factor_table[num].first);
        num = factor_table[num].second;
    } while (num != 1);
    return factors;
}

我相信它会比你的快得多，因为我能够避免使用除法(/和%)。事实上，我也不使用任何乘法。

(使用g++比问题中的代码快约6倍，实际的因子生成部分比lol4t0's略快10%。std::vector<int>中的返回因子要比生成因子的时间长5倍。)

测试程序：http://ideone.com/pt9nu

原申请书：

• http://ideone.com/Weeg6

Answer 2

从我的头顶上，一旦你找到一个因素，你可以在你现有的桌子上查找。这将使你不必继续寻找更多的质数。

Answer 3

关于优化问题：

• 您使用的是push_back，而不保留任何内存。你确定你不想先预留一些你认为安全的金额吗？
• 通过使用模和除法来检查某物是否为2的倍数。您的编译器可能已经对此进行了优化，但只要您知道数字不是负值，就可以使用按位移位和右移。
• 在一个内部循环的每一次迭代中，您都会将j与自身相乘。存储ceil(sqrt(num))可能更有效。
• 重新阅读时，我看到您在第二个循环中使用i做同样的事情。

除此之外，您可能应该看看以下几个问题：

• 不允许声明没有返回类型的main。
• 不建议使用样式header.h的C头，现在使用cheader。(例如，cmath而不是math.h。)正如Ben所言，您没有使用任何来自您的包含的内容，所以您应该完全放弃它们。
• 你有using namespace std;。虽然这对于一个简短的程序来说是可以的，但是它不能很好地与全局变量结合在一起，并且显式限定名称在这种情况下会更有意义(无论如何，您只有5个名称需要限定)。
• 计算素数的线条对我来说是不可读的。由于您可以确保循环的主体总是在增量之前执行，所以可以将其更改为for (int j = i+i; j < lim; j += i) prime[j] = 0;，这将在提高其可读性的同时执行相同的操作。对于第一个循环，也可以做类似的事情。
• 将这些代码分解成函数会有很大帮助。考虑到大多数变量都是全局的，您唯一需要担心的就是函数调用开销(如果函数是内联的，这可能是不存在的)。特别是，我会搬出calculate_primes。
• 您没有在任何地方使用pan，所以您不应该首先声明它。