Question

C语言因式分解

用C语言编程将2到n的所有数因式分解，如输入n=6，输出:
2=2
3=3
4=2*2
5=5
6=2*3
程序效率要尽量高，比如我同学的笔记本CPU是T6670输入100000，用不了1分钟就全部输出，最好能在半分钟内输出2到100000

Answer 1

// 下面是用我在toj 10004上面通过的代码，稍加修改写成的。
#include <stdio.h>
#include <math.h>
int Prime(int x)
{
int n, i;
n = (int)sqrt(x);
for (i = 2; i <= n; i++)
if (x % i == 0) break;
if (i > n)
return 1;
else
return 0;
}
int main()
{
// freopen("2.txt","w",stdout);
int x;
int t;
int i , n;
int y;
int first;
int max;
while (scanf("%d",&max) == 1)
{
for (y = 2; y <= max; y++)
{
x = y;
if (Prime(x))
{
printf("%d=%d\n",x,x);
}
else
{
printf("%d=",x);
first = 1;
do
{
for (i = 2; i <= x; i++)
{
t = 0; n = 0;
while (x % i == 0)
{
t = 1;
n++;
x = x/i;
}
if (t)
{
if (first) first = 0;
else printf("*");
while (n>1)
{
printf("%d*",i);
n--;
}
printf("%d",i);
}
}
} while(x != 1);
printf("\n");
}
}
}
return 0;
}

Answer 2

半分钟...
这也太低估现在CPU的计算能力了
楼上这个已经是效率低下的方法了, 我这里输入100000往硬盘输出, E8400 + ST3160815AS输出也就不到3秒的事情

Answer 3

楼上什么机器
这么快

Answer 4

#include"iostream.h"
main()
{
int n,t;
int a[13];
cin>>n;
for(int r=2,t=0;r<=n;r++)
{if(n%r==o)a[t]=r,t++;
}
cout<<n<<'='<<a[0];
for(t=1;t<=13;t++)
{if(a[t]!=0)cout<<'*'<<a[t];
}
cout<<endl;
}