| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2803 人关注过本帖
标题:学习日记三:素因子分解,撸了一个上午
只看楼主 加入收藏
令狐少侠56
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:320
专家分:175
注 册:2014-4-10
收藏
得分:0 
回复 15楼 wmf2014

现在有若个疑问:
1.
那个程序是怎么判断素数的,我试画了9,15运行流程图还不知道原因
是通过这句筛选么,for(i=j;(i*i<=n)&&(n%i);i++);怎么判断的?
2.
这里由于递归函数并未放在for循环内部,并且是尾递归,那么运行到递归出口后返回上一层,
不会执行任何语句,一直返回直到第一次调用,整个递归函数结束。所以这里递归函数返回没有可能
改变数组中数据。。。。。这算不算是一个技巧。。
2015-11-06 11:29
令狐少侠56
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:320
专家分:175
注 册:2014-4-10
收藏
得分:0 
回复 20楼 TonyDeng
不明觉厉。。。
2015-11-06 11:30
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 21楼 令狐少侠56
1,无需刻意判断素数,一个合数的最小因数肯定是素数(查了下,好像没这个说法,但经得起验证),当这个数没有因数时他本身就是素数。
2,for(i=2;(i*i<=n)&&(n%i);i++);这个循环退出条件是找到最小因数(条件n%i)或这个数已经是素数(条件i*i<=n),所以这个循环结束后,如果i*i>n则说明n为素数,否则i就是n的最小因数。
3,递归只发生在找到最小素数时,此时n可以整除i,i是最小素数。首先将最小素数存入数组,然后数组指针递增后递归。
4,当n为素数后递归结束,n为最后一个因数,把n存储进数组,逐级退出递归。
以上就是我的代码递归找质因数的大致思路,关键是一个合数的最小因数是素数的观点减少了很多重复判断代码。另:即使是找无符号的32位的最大质数用电脑运算也是很快的,因为只是判断一个数是否为质数,无需采取查表法,如果是判断32位数的范围内有多少个质数,这种方法就比查表法慢多了,用筛法建表也不合适,因为需要4g内存空间,估计可以像T版那样建个素数表查找,百度了下,10亿内的素数有50847534个,约占204兆字节,不知道读这么大的文件要多长时间。

能编个毛线衣吗?
2015-11-06 12:44
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25859
专家分:48889
注 册:2011-6-22
收藏
得分:0 
64位的素數表再大,也不需要讀入内存中,一次衹讀8字節遞進。何況還有分段儲存文件的手段。能寫直接代碼就盡量寫。

授人以渔,不授人以鱼。
2015-11-06 13:21
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25859
专家分:48889
注 册:2011-6-22
收藏
得分:0 
我那個,是用已排序的素數逐個除原數,除得盡多少個就記下次數,不斷縮小原數,直至得到1爲止,屬於直接代碼。由於除數全是素數,所以不用不可靠的假定前提。這個算法,無論多大的大數都是同樣的速度。最關鍵的是,這樣得到的結果,可供程序後續任意使用,修改、維護都非常方便。

這個算法,不用C,就算是解釋語言,也夠快,因爲基本上沒運算。

價值在那張素數表上,一輩子可用,每次都去算它幹嘛,那算法也不值錢,開源又如何。

[此贴子已经被作者于2015-11-6 13:49编辑过]


授人以渔,不授人以鱼。
2015-11-06 13:35
令狐少侠56
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:320
专家分:175
注 册:2014-4-10
收藏
得分:0 
回复 25楼 TonyDeng
两个版主都强。。。。。
2015-11-06 16:48
令狐少侠56
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:320
专家分:175
注 册:2014-4-10
收藏
得分:0 
回复 23楼 wmf2014
有那种可以提高编程技巧的书籍推荐么。。。
2015-11-06 16:50
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25859
专家分:48889
注 册:2011-6-22
收藏
得分:0 
對於那些快速算法,我們總是可以拿一些速度差不多但是更容易理解的算法來替代它們。

授人以渔,不授人以鱼。
2015-11-06 21:47
快速回复:学习日记三:素因子分解,撸了一个上午
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.114148 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved