【佛山网址之家-佛山网址大全】佛山实用网址,搜索大全尽在fs218.com(Foshan)欢迎您!
网站首页
新闻报刊
数码产品
文学小说
财经股市
娱乐明星
幽默笑话
医疗保健
政府组织
法律资讯
男士女性
编程设计
科技IT
军事资讯
家庭理财
两性健康
汽车资讯
营养美食
人才市场
考试考研
艺术爱好
星座命理
美女帅哥
体育资讯
时装时尚
少年儿童
宠物花鸟
您现在所在位置:主页 > 编程设计 >

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

发布时间:2019-05-12  来源:未知  作者:木木

题目:

输入一个正整数,用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的所有质因子都找到了

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





上一篇:Python基础练习实例49(打印杨辉三角)
下一篇:没有了

今日推荐

粤港澳大湾区智能精
广州5月7日电 (记者 唐贵江)“服务粤港澳大…[详细]
科技赋能 “云”助
福州5月7日电 (叶秋云)5月7日上午,第二届…[详细]
BrandZ中国品牌100
客户端北京5月6日电 传播服务集团WPP与调研…[详细]
美团外卖日完成订单
美团开发布会推出新品牌美团配送。图为美团…[详细]
中国声谷人工智能产
安庆5月1日电(张俊)中国声谷人工智能产品太…[详细]
中国华为在巴西推出
中新社圣保罗4月30日电 (记者 莫成雄)当地…[详细]
还在研究MacBookPro
4月29日电 华为P30超长变焦系统在手机影像…[详细]
中国电信实现杭州核
中国电信实现杭州核心区域5G信号连续覆盖 …[详细]
赶快检查!你可能在
使用微信时总弹出广告,不小心就点到不知名…[详细]
爱分析中国数据智能
2019是大数据行业迈入深化发展的开端,也被…[详细]
OPPO携中国联通共建
4月24日电 今日,OPPO广东移动通信有限公司…[详细]
魅族16s旗舰手机正
4月24日电 23 日,魅族科技(Meizu)在珠海正…[详细]
友情链接:
  • 广美举办学院当代教育国际研讨会 主题聚焦“抽象艺术
  • 第十届中国卫星导航年会五月下旬将在北京举办
  • 长三角“G60科创走廊”:冲破“堵点”找“融点”
  • 角膜上皮干细胞移植给患者带来光明
  • 万博bet官网
  • 时时彩注册送47元彩金
  • 大乐透历史开奖号码
  • 白金会娱乐集团
  • 网上真钱扎金花
  • 888真人备用网址
  • 老虎机作弊器
  • 福彩3d谜语