标题:用删除法编写一个制作素数表的vfp程序
只看楼主
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:57
帖 子:713
专家分:556
注 册:2016-6-29
结帖率:100%
已结贴  问题点数:20 回复次数:157 
用删除法编写一个制作素数表的vfp程序
标记法主题思路,标记法是把符合条件的标记为假flase,而不符合条件的标记为真,在vfp中是这样实现这个过程的,先用
本轮参与运算的,求出最大开方值,然后查出所在记录条位置,由此记录条作为筛选循环总次数,第一次现由源数据,加周
期值9699690(即2*3*5*7*11*13*17*19=9699690,一次性调入1658880个数据(就这些需要判断是否为素数,其余的已经被排
除掉了)。有了循环次数,有了被筛选数据,进入主要循环体,先调入第一个素数,划掉其倍数,其余的存入数据b(从数据
源先调入数据a),然后调入第二个素数,排查数据b中符合条件的,剩余的存入数据a(当然每次存数据以前,要把数据表先
清空),循环往始,直到调入最后一个素数为止。然后把最后存的数据,抄写到素数结果表。
进入下一批数据调入,即把数据源加一个周期值9699690,先判断开方值,把小于等于开方值的记录条作为本次的素数调入个
数的依据(即本次的排查次数),进入同样的循环,获得结果,抄写到素数结果表。直到全部周期结束为止。
外循环为周期数,内循环为开方值记录条数减去素数19前的个数8,比方开放值以内有1000个素数,则内主体循环次数为:
1000-8=992次,当然随着循环周期的扩大,内循环次数增多。内循环单次,需要判断值逐步减少,例如第一次调入1658880个
值,大概有1658880/23=72125数被去掉,1658880-72125=1586755/29=54715数被筛掉,这样下去,越往后被判断数越少。所以
成倒排三角形数据量。把最后剩余的数据存放在素数结果表中即可。
外循环步长9699690,即一次性可以判断这样的自然数段。
最原始的筛法,一个一个的去判断,筛除,也就是都在重复同一项工作,效率低下;而这种算法是一次性调入一个批次的数据(这个批次是一个自然数段落,一个递增周期),是众数,不是一个一个的来,而是一同进入,然后第一次就排除了,最多的数据(因为小素数先参与排查,根据几率均等原则,它的倍数最多)。
搜索更多相关主题的帖子: 判断 素数 周期 循环 数据 
2021-09-13 21:47
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:57
帖 子:713
专家分:556
注 册:2016-6-29
得分:0 
编写思路:预先制作一个5万以内的素数表,做为内循环调用素数之用,在做一个素数表(盛放素数,即把结果抄写到此表),有一个数据源表,就是基础数据(被2,3,5,7,11,13,17,19筛除过的,剩余自然数(9699690以内,它是一个外循环需要增加的值)),数据源中有2*4*6*10*12*16*18=1658880个数据,每增加一次外循环,所有数据源中的数加9699690一次,即被筛选数据=数据源中的数+(i-1)*9699690,i为外循环值;判断每批次调入的最大值的开方值,用count 函数求出小于等于它的记录条数,比如外循环值i=1时,数据源中的最大值9699689,开方值3114.4,在素数表中找到小于等于它的记录条数:443(最后一个满足条件的素数是3109),把此数443-8(不必检查素数2,3,5,7,11,13,17,19这八个素数,因为数据源的数据就是它们制作出来的,也就是说已经通过了它们的筛选,不可能还有它们中的因子,外循环每次增加值是它们的公倍数9699690,所以仍就不含其因子),这样内循环就是443-8=435,把指针移到记录条9的位置(go 9→即从素数23开始),建一个表"数据a",再建一个表"数据b",每一次外循环开始,先清除“数据a”的记录值(只留表结构,把数据标记删除,然后在彻底删除),之后把数据源的记录值+(i-1)*9699690追加新记录,这步完成后,进入内循环子程序,调入第一个素数23(go 9),判断“数据a”的数值是否整除它,整除的直接跳过,不做存表处理,不能整除的,在“数据b”中增加一条记录,把值赋给“数据b”中新增记录条,然后第二个素数调入,以“数据b”为参考,进行同样的处理,循环往复,直到调入本次内循环最后一个素数,然后把最终结果抄写到素数表结果中存储。进入下一个外循环。

素数问题的解决是我学习编程永恒的动力。
2021-09-13 22:29
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:57
帖 子:713
专家分:556
注 册:2016-6-29
得分:0 
所用素数表和数据源表:
数据源.zip (2.2 MB)
素数表.zip (9.49 KB)

素数问题的解决是我学习编程永恒的动力。
2021-09-13 22:31
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:57
帖 子:713
专家分:556
注 册:2016-6-29
得分:0 
大概思路就是这样,相关表和数据已经有了。把外循环次数控制在2以上即可。
整个思路就是网上的划掉法,把n以内的数据排列好,然后从素数2开始划掉后边2的倍数,接着划掉3的倍数,继续....,划掉最后一个素数的倍数(根号n内的最后一个素数的倍数)。只是把这种方法,做了一个折中方法,如果n值较小,可以一次性处理完成,可是当n较大时,我们可以分段处理,另外为了降低运算时间,提前对每段做了预先处理,因为小素数排除的数比重较大,所以我把处理批次的量定在9699690这个增加周期上,在它每一个周期内只需要处理:2*4*6*10*12*16*18=1658880个数据,占比1658880/9699690=0.171多点,大大节约了时间,在就是一个一个的判断,要比这种成批的计算,费时的多。数据a和数据b是相互替换的,每参与一个素数,它们的记录条都会减少,所以也会大大的缩短时间(不必每次都把所有数据判断一次了,已经不符合的干脆去掉,越来越轻装上阵)。

素数问题的解决是我学习编程永恒的动力。
2021-09-13 22:55
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:57
帖 子:713
专家分:556
注 册:2016-6-29
得分:0 
有人浏览了,没有进行提问,也不知道是否理解问题?有不清楚的地方,我希望大家问出来,我好针对的回答。就是二层循环,外层循环就是成批的调入数据,内循环是主角,虽然没有按网上的把记录条标记真与假,用求余数法去掉了被筛除数,道理是一样的,对于内循环次数也容易获得。不知大家怎么看?

素数问题的解决是我学习编程永恒的动力。
2021-09-14 07:11
schtg
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:https://t.me/pump_upp
等 级:贵宾
威 望:67
帖 子:1355
专家分:2534
注 册:2012-2-29
得分:2 
学习之中
2021-09-14 07:48
mywisdom88
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:190
帖 子:3125
专家分:8340
注 册:2015-3-25
得分:3 
语文水平有限,不知道你说什么,你要做什么。。。
2021-09-14 08:41
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:57
帖 子:713
专家分:556
注 册:2016-6-29
得分:0 
回复 6楼 schtg
如果理解了,我希望尽早得到回复。

素数问题的解决是我学习编程永恒的动力。
2021-09-14 08:45
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:57
帖 子:713
专家分:556
注 册:2016-6-29
得分:0 
回复 7楼 mywisdom88
就是用划掉法制作素数表。用筛选法制作素数表,是每调入一个正整数,把它开方值以前的素数都用一遍,中间时,有整除的直接跳出循环,然后筛选下一个值。
而此种方法就是一下子调入一批数(假如100个正整数或者1千个,甚至更多),求出此批次最大一个值的开方数,找到开方值以前的所有素数(即素数≤根号n(n是这批次的最大值)),确定最后一个符合条件的素数所在的记录条,以此记录条作为内循环值(循环次数),因为数据源是经过素数2至19处理的,所以不在做检验,直接从第9个素数23开始,进入内循环即可,所以内循环次数-8,在内循环中有两个表,目的是盛方待处理数据,每次外循环进入前,先把数据调入数据a表,然后调入第一个条件素数23,进行筛选,把23的倍数去掉后,剩下的被筛选数据放到数据b表中,调入下一个素数29,筛选数据b表中的数,把被29整除的去掉,剩下存放在数据a表中(当然存前需要清空数据,在第一步时一样,先清空数据b表),数据a与数据b来回互换,当筛选完后,判断筛选次数是奇数还是偶数,根据奇偶性,可以判断出那个表中的数据为最终结果,然后把结果抄写到素数表结果中即可,完成本次外循环,进入下一个外循环值,进行同样步骤。
如果还是不理解,可以针对性提问。
说起语文水平,我更是一般,只能是中下水平,语言表达,也是不到位,无法准确无误表达我的想法和思路,沟通起来有点费劲。

素数问题的解决是我学习编程永恒的动力。
2021-09-14 09:14
xuminxz
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:40
帖 子:749
专家分:2475
注 册:2011-5-8
得分:3 
最基本的问题我不明白。
楼主是向我们介绍一个程序吗?可没有看到啊。
是想让大家帮忙写个程序吗?可你不是已经有了吗?(结果都出来了呀。)

dBase有人接盘了。
2021-09-14 09:32



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-506838-1-1.html




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

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