关于质因数分解，对以下程序不解解决思路

关于质因数分解，对以下程序不解

C/C++ code

#include<iostream>using namespace std;int f(int n){    int nt = n;    int cnt = 0;    for(int i = 2; i <= nt;i++)        if(!(nt%i)){            cout<<i<<" ";            cnt++;            nt = nt/i;            i = 1;        }    cout<<endl;    return cnt;}int main(){    int n;    while(cin>>n){        cout<<f(n)<<endl;    }    return 0;}

我感觉这个程序很诡异，不太明白原理，

Q1.一个是并没有进行素数判定，如何保证输出的i是素数？
Q2.为什么n/=i后i的起点要修改为1，而改成2则不正确。

望高手帮助解释一下

[解决办法]
Q1.一个是并没有进行素数判定，如何保证输出的i是素数？
如果i是合数，则一定存在一个比i小的质数可以被nt整除，如果有的话在之前已经被除过了，因此不会出现合数。

Q2.为什么n/=i后i的起点要修改为1，而改成2则不正确。
改为1之后，后面就又从2开始试除了，如果改成2则是从3开始试除，如果某个数是4的倍数，就会出错了。
但这种写法效率还是比较低，应该改为i--
[解决办法]
感觉写的不是太好。
每次i都从头开始。
i = 1
改成 i -- 会更好一点。

Q1：
不需要判定，因为是从小到大的进行枚举的。若i不是素数，则i的质因数必定会在之前已经被分解出来了，因此不可能可以整除nt。

Q2:
由于循环体执行以后都会执行 i++,因此如果i = 2，则执行i++ 后会变成3，导致2被越过。


[解决办法]
i <= sqrt(n)
[解决办法]
你的程序效率太低了,
当有超过1000的的质数 时候就开始受不了了

C/C++ code

vector<unsigned int> v;int f(int n){    v.clear();    while(!(n%2)){        v.push_back(2);        n /= 2;    }    for(int x = 3;x <= sqrt(double(n)); x += 2){        while(!(n%x)){            v.push_back(x);            n /= x;        }    }    if(n != 1)        v.push_back(n);    //for(vector<unsigned int>::iterator p = v.begin();p != v.end();++ p)    //cout<<*p<<" ";    //cout<<endl;    return v.size();}
[解决办法]
如果要这样，i*i <=n效率要高很多，sqrt是个复杂得计算
探讨

i <= sqrt(n)

[解决办法]
探讨

i <= sqrt(n)

[解决办法]
大素数分解在计算机代数这门学科里面有成熟的算法，一般符号计算软件（如maple）都可以实现，过程很复杂，用到很高的数学知识，不是几句话可以说清楚的
普通的算法复杂度都太高了
[解决办法]
呵呵，帮顶 

 

查看更多 下一篇