分解质因数算法

时间:2021-06-24 11:25:59

题目:将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。

分析:从1到N先找出最小的质因数,如果等于本身,那么说明只有一个质因数,如果不是,那么将该质因数打印出来,并将N/该质因数作为新的N值进行运算。

设计步骤:

  1、如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可。

  2、如果n!=k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你n,重复执行第一步。

  3、如果n不能被k整除,则用k+1作为k的值,重复执行第一步。

代码实现:

#python版

def count_number(value):
n
= 2
while n <= value:
while value != n: # 如果value等于n,说明只有一个质因数,否则就进行循环
if value % n == 0: # 说明n为一个质因数
print(n)
value
= value / n # 更新下一轮value的值
else:
break
n
+= 1
print(n-1) # 打印出最后一个值
#Cpp版


//将一个正整数分解质因数
int main()
{
int i,n;
printf(
"Please input an integer!\n");
scanf(
"%d",&n);
for(i=2;i<=n;i++)
{
while(n!=i) //若i=n,则质因数就是n本身
{
if(n%i==0) //若i是质因数,则打印出i的值,并用商给n赋新值
{
printf(
"%d\n",i);
n
=n/i;
}
else break;//若不能被i整除,则算下一个i
}
}
printf(
"%d\n",n); //这里是打印最后一个质因数,也就是等于i时的那个
return 0;
}