学步园

把一个整数分解为素数相乘

个人感觉效率还可以。

复杂度，取决于这个整数的组成。

一般情况下就是素数个数+判断最大素数因子为素数 的复杂度吧！

#include <stdio.h><br /> #include <math.h><br /> #define MAX 128</p> <p>#define NUMBER 250<br /> int isteps = 0;<br /> //分解因式，打印出来<br /> void breakNumber(int num)<br /> {<br /> int i;<br /> int left;</p> <p> left = num;<br /> for(i = 2; i<=sqrt(left);i++)<br /> {<br /> isteps++;<br /> //除掉所有i<br /> while(0 == left%i)<br /> {<br /> printf("%d/n",i);<br /> left /= i;<br /> isteps++;<br /> }<br /> }</p> <p> if (left!=1 || num == 1)//need not 1 any more<br /> printf("%d/n",left);</p> <p> printf("All:%d/n",isteps);<br /> }<br /> //分解因式、保存到数组，和上面那个差不多，就是改了输出方式<br /> int resolveNumber(int num, int out[])<br /> {<br /> int i;<br /> int left;<br /> int totalNumber = 0;<br /> left = num;<br /> for(i = 2; i<=sqrt(left);i++)<br /> {<br /> while(0 == left%i)<br /> {<br /> //printf("%d/n",i);<br /> out[totalNumber++] = i;<br /> left /= i;<br /> isteps++;<br /> }<br /> }</p> <p> if (left!=1 || num == 1)//need not 1 any more<br /> {<br /> out[totalNumber++] = left;<br /> }<br /> return totalNumber;<br /> }<br /> int main()<br /> {<br /> int i =0;<br /> int geneNumber = 0;<br /> int genes[MAX] = {0};</p> <p> //breakNumber(NUM);<br /> geneNumber = resolveNumber(NUMBER,genes);<br /> printf("geneNumbers:%d/n",geneNumber);<br /> for (i = 0; i< geneNumber; i++)<br /> {<br /> printf("%d/n",genes[i]);<br /> }</p> <p> return 0;<br /> }