## BASIC-16 分解质因数（名字防止重复）

约定不等于承诺〃 2022-12-10 14:47 108阅读 0赞

## BASIC-16 分解质因数 ##

思路：  
思路就是没有思路  
直接暴力枚举  
但是其实可以 利用之前的结果节省运算  
**这里参考了别人的 质数表生成的函数**  
比如FactorTable\[8\] = ‘2’ + FactorTable\[4\];

const int maxn = 10000;
    int prime[maxn];
    void makeprime()//生成质数表的子函数
    {
        int j, n = 29, i = 9, sqrtn;//从第10个质数开始计算，第10个质数是29
        prime[0] = 2;
        prime[1] = 3;
        prime[2] = 5;
        prime[3] = 7;
        prime[4] = 11;
        prime[5] = 13;
        prime[6] = 17;
        prime[7] = 19;
        prime[8] = 23; //之前已有9个质数在表中
        while (i < maxn) //i是计数变量
        {
            j = 0; //每次从表头开始试除
            sqrtn = sqrt(n); //n的平方根
            while (prime[j] <= sqrtn)
            {
                if (n % prime[j] == 0)break; //若n能整除质数表中的某数，则跳出
                j++;
            }
            if (prime[j] > sqrtn) { prime[i] = n; i++; }
            n += 2; //除了2，偶数不会是质数，因此跳过所有偶数
    
        }
    }
    
    map<int, vector<int> >  FactorTable;
    int main()
    {
    	ios::sync_with_stdio(false);
        makeprime();
        int a, b;
        cin >> a >> b;
        for (int i = a; i <= b; i++)
        {
            int num = i;
            while (num != 1)
            {
                int j = 0;
                while (1)
                {
                    if (num % prime[j] == 0)
                    {
                        FactorTable[i].push_back(prime[j]);
                        num /= prime[j];
                        break;
                    }
                    j++;
                }
            }
        }
        for (int i = a; i <= b; i++)
        {
            cout << i << '=';
            for (int j = 0; j < FactorTable[i].size(); j++)
            {
                if (j) cout << '*';
                cout << FactorTable[i][j];
            }
            cout << endl;
        }
    	return 0;
    }