题目:

输入一个正整数,用Scratch编写程序,按照从小到大的顺序输出它的所有质数的因子(如180的质数因子为2 2 3 3 5 );

常规思路每一次遍历一遍2到N的全部的整数,找到一个质数因子a,然后将N设置为N/a,直到N等于1,但是这种方法其实就是暴力搜索,时间效率并不好。

其实有一种更好的方法,就是设定i=2,i一直递增,当N除以i余数为0的时候,N设定为N/i,否则i++,直到i>N,这样找到的所有N除以i余数为0的i就是N的所有的质数因子

这样为什么可行呢?

我们假设从2开始,找到的第一个N除以i余数为0的i为a1,首先a1一定是质数,因为假如a1是合数的话在2和a1之间一定存在其他N可以整除的质数,但是i是从2开始找到的第一个可以整除的数,因此i只能是质数,也就是说i是N最小的质因子

我们将N设定为N/i

然后从a1继续往后找,找到第二个N可以整除的数a2,a2不可能是合数,因为假如a2是和数的话,2到a1,或者是a1到a2之间一定存在没有分解的质数,而这是不可能的,所以a2一定是质数,且是N第二大的质因子,进行将N设定为N/a2

继续以上操作,当找到最后一个质因子的时候,N==i,这个时候算法结束,至此,N的所有质因子都找到了

除了这种思路你还有什么更好的算法呢?请大家晒出各自的算法,可以将结果上传到我们的网站。我们将隔日公布参考答案。

程序截图如下(源码下载

scratch算法练习-整数的全部质数因子