2019年11月

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;
}

IMG_20191114_210812.jpg

a 算法实现

#include<iostream>

class numbertheory {
public:
    typedef struct solveStruct{
        int g,x,y;
        solveStruct(int gg,int xx,int yy)
        {
            g = gg;
            x = xx;
            y = yy;
        };
        solveStruct()
        {
        };
    } solvestruct;
    //calculator of ax+by=gcd(a,b)
    solveStruct solveProcess(int a,int b){
        int x = 1;
        int g = a;
        int v = 0;
        int w = b;
        int y,s,t,q;
        while(1)
        {
            if(w==0)
            {
                y = (g-a*x)/b;
                return solveStruct(g,x,y);
            }
            t = g % w;
            q = (g - t) / w;
            s = x-q*v;
            x = v;
            g = w;
            v = s;
            w = t;
        }
    }
};
int main()
{
    numbertheory nt;
    int a,b,g;
    std::cin >> a >> b >> g;
    numbertheory::solveStruct st;
    st = nt.solveProcess(a,b);
    std::cout << st.x << " " <<st.y<<" "<<st.g;
    return 0;
}

计算下面式子的整数解
(19789,23758)
(x,y,g) = (1303,-1905,7)
(31875,8387)
(x,y,g) = (-381,1448,1)
(2241739,19848039)
(x,y,g) = (3939958,-95,1)

修改a或b为0时候无结果的问题

//add after cin
if(~a|b)
{
 a==0 ? std::cout << "X takes any value y=1 g=1": std::cout << "Y takes any value x=1 g=1";
return 0;
}

修改程序使得输出总大于0

.........
if(w==0)
{
    y = (g-a*x)/b;
//start add code
    while(x<0)
    {
        x = x+b;
        y = y-a;
    }
//end
    return solveStruct(g,x,y);
}
t = g % w;
q = (g - t) / w;
.........