7.编写将正整数n分解成素数乘积的程序
IMG_20191117_005651.jpg

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
class mathTheory {
    vector<int> p,k;
    vector<int> primeTab;

    public:
    mathTheory(){
        p.clear();
        k.clear();
        primeTab.clear();
    }
        //simplest way
        void resolv_simple(int n)
        {
            if(checkisPri(n))
                {
                    p.push_back(n);
                    k.push_back(1);
                    return;
                }
            for(int i=2;i<=n;i++)
            {
                if(checkisPri(n))
                {
                    p.push_back(n);
                    k.push_back(1);
                    break;

                }
                if(checkisPri(i))
                {
                    int tk=0;
                    if(n%i==0)
                    {
                        p.push_back(i);
                    while(n%i==0)
                    {
                        n = n/i;
                        tk++;
                    }
                        k.push_back(tk);
                    }
                }
            }

        }
        int checkisPri(int p)
        {
            if(!primeTab.size() > 0)
            {

            for(int i=2;i<p;i++)
            {
                if(p%i==0)
                {
                    return 0;
                }
            }
            return 1;
            }
            else
            {
                for(vector<int>::const_iterator tp =primeTab.begin();tp!=primeTab.end();tp++)
                {
                    if(p%*tp==0)
                    {
                        return 0;
                    }
                }
                for(int i=100;i<sqrt(p);i++)
                {
                    if(p%i==0)
                    {
                        return 0;
                    }
                }
                return 1;
            }
        }
        //generate table before resolv
        void resolv_better_method(int n)
        {
            genTab(100);
            int sn = sqrt(n)+1;
              if(checkisPri(n))
                {
                    p.push_back(n);
                    k.push_back(1);
                    return;
                }
            for(int i=2;(i<sn &&i<=n);i++)
            {
                if(checkisPri(n))
                {
                    p.push_back(n);
                    k.push_back(1);
                    break;

                }
                if(checkisPri(i))
                {
                    int tk=0;
                    if(n%i==0)
                    {
                        p.push_back(i);
                    while(n%i==0)
                    {
                        n = n/i;
                        tk++;
                    }
                        k.push_back(tk);
                    }
                }
            }
        }
        void genTab(int tabsize)
        {
            for(int i=1;i<tabsize;i++)
            {
                if(checkisPri(i))
                {
                    primeTab.push_back(i);
                }
            }
        }
        //beauty output
        void output_solve()
        {
                int count = p.size();
                for (int i = 0; i < count;i++)
                    {
                    cout << p[i] ;
                    if(k[i]>1)
                    {
                        cout << "^"<<k[i];
                    }
                    if(i!=count-1)
                    {
                         cout << "*";
                    }
                    else
                    cout <<endl;
                    }
        }
};
int main()
{
    int m;
    cout <<"use better way?";
    cin >> m;
    int n;
    cin >> n;
    cout <<n <<"=";
    if(n>0)
    {
    mathTheory mt;
    if(m==0)
    mt.resolv_simple(n);
    else
        mt.resolv_better_method(n);
    mt.output_solve();
    }
    else
    {
        cout << "ERROR";
    }
    return 0;
}

标签: none

发表新评论