首先介绍质数,及只能被1和自己整除的数。
任何一个自然数都能够分解成质数的乘积,比如100=2*2*5*5, 9990=2*3*3*3*5*37。
我的算法非常简单,以下是主要步骤:
1、现有一个待分解的数假设是n(n>2),拿这个数不断的去除i(i的初始值为2且递增,2<i<n,当然为了优化算法也可以将i的取值范围限制为2<i<=n/2,举个例子,100要能整除一个数,这个数要是超过了100的一半50,还怎么整除),n除i之前先判断i是否满足前面括号内的条件,要是满足就除,要是不满足就结束;
2、将整除后的值重复步骤1(递归调用);
废话不说,直接上代码:
class Program { static void Main(string[] args) { try { int a = Convert.ToInt32(Console.ReadLine()); fun(a); } catch (Exception) { Console.WriteLine("输入不合法!"); } } private static void fun(int a) { for (int i = 2; ; i++) { if (a > i)//这里可以坐下优化工作 { if (a % i == 0) { Console.WriteLine(i); a = a / i; fun(a);//递归调用 } } else { Console.WriteLine(a); Environment.Exit(0); } } } }