| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 10234 人关注过本帖
标题:用删除法编写一个制作素数表的vfp程序
取消只看楼主 加入收藏
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:71
帖 子:797
专家分:683
注 册:2016-6-29
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:98 
用删除法编写一个制作素数表的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
来 自:河北省曲阳县
等 级:版主
威 望:71
帖 子:797
专家分:683
注 册: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
来 自:河北省曲阳县
等 级:版主
威 望:71
帖 子:797
专家分:683
注 册:2016-6-29
收藏
得分:0 
所用素数表和数据源表:
数据源.zip (2.2 MB)
素数表.zip (9.49 KB)

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

素数问题的解决是我学习编程永恒的动力。
2021-09-14 07:11
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:71
帖 子:797
专家分:683
注 册:2016-6-29
收藏
得分:0 
回复 6楼 schtg
如果理解了,我希望尽早得到回复。

素数问题的解决是我学习编程永恒的动力。
2021-09-14 08:45
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:71
帖 子:797
专家分:683
注 册: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
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:71
帖 子:797
专家分:683
注 册:2016-6-29
收藏
得分:0 
回复 10楼 xuminxz
大概流程是那样的。当然是想让大家安照这种方法方式编写一个vfp程序,以便优化,使程序运算时间大幅度降低。一个一个的筛太慢了,我等不及,想尽快获得结果,得到数据。

素数问题的解决是我学习编程永恒的动力。
2021-09-14 11:02
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:71
帖 子:797
专家分:683
注 册:2016-6-29
收藏
得分:0 
回复 11楼 laowan001
把1至3连起来就是我的意思。

素数问题的解决是我学习编程永恒的动力。
2021-09-14 11:03
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:71
帖 子:797
专家分:683
注 册:2016-6-29
收藏
得分:0 
CLEAR
SELECT 1
USE D:\vfp温习\素数式至17表.DBF ALIAS 素数式表
SELECT 2
USE D:\vfp温习\素数表万3.DBF ALIAS 素数表万3
SELECT 3
USE D:\vfp温习\素数表亿新.DBF ALIAS 素数表亿新 &&当时仅改变了别名,没有改原名,在素数表亿新后增加了198-200周期素数,改正,并去掉了后续素数
*INPUT "请输入预先值 K= " TO yxk
*INPUT "请输入步长值 bcz= " TO bcz
*INPUT "请输入初始值 csz= " TO csz
*INPUT "请输入外循环起始值 xks= " TO xks
*INPUT "请输入外循环终结值 zds= " TO zds
bcz=510510  &&从2乘到17,即素数17的素数阶乘
kssj=SECONDS()                      &&取出开始时间
FOR i=198 TO 200
@12,10 SAY i
            &&调了下顺序,原来在FOR j=1 TO 92160 的下边,执行第一个外循环,提示已经到了表尾
FOR j=1 TO 92160
SELECT 1
GO j
sss=素数式
bpz=sss+(i-1)*bcz               &&计算被判断值
Kf=INT(SQRT(bpz))                   &&求出被判断值的开方根
SELECT 2
GO 1
COUNT ALL FOR 素数<=kf TO jlh  &&借用原来的记录号,实际上统计kf以前的素数个数
  && jlh=RECNO()
SELECT 2   
GO 7                                &&从第二条记录开始读取素数(3)
FOR k=1 TO jlh-6                     &&内循环开始。这个循环实质上是从小到大顺序,依次读取素数。循环值是记录序号
qmz=MOD(bpz,素数)                   &&以读取的素数为条件,对被判断值求模
IF qmz=0 && OR qmz=2 OR qmz=6 OR qmz=8  如果符合这四个约定条件之一,就进行相应工作.如果一个也没有符合条件的,直接使记录指针向下移动一个(SKIP)
EXIT                                &&因为符合条件,则做完相应工作后跳出内循环
ENDIF
SKIP                                &&素数表指针向下移动一个
ENDFOR
IF k>jlh-6
SELECT 3               &&打开保存求解结果的信息表
APPEND BLANK                        &&增加一条空记录
REPLACE 素数 WITH bpz && 把bpz赋给素数        
ENDIF
ENDFOR
ENDFOR
=MESSAGEBOX("运行时间:"+LTRIM(STR(INT((SECONDS()-kssj)/60)))+"分"+LTRIM(STR(MOD(SECONDS()-kssj,60),5,2))+"秒",64,"运行时间提示")
这是一个制作素数表程序,也用到数据源表(素数式至17表→即用素数2,3,5,7,11,13,17这7个素数处理过的数据,每一层外循环数值增加值是510510(2*3*5*7*11*13*17),中层循环为92160(2*4*6*10*12*16),最;里层循环次数不定,有被判断值的开方值前素数个数确定最大循环次数,合数循环次数都小于最大循环次数,只有质数才是满循环),只不过,这个程序是一个一个的判断,排除,筛选。
而本帖要求一次性调入92160个数据(即中循环次数),在主要循环体中,是每次都得全部未完成,并不退出循环(循环次数以最大次数为准(不考虑那一批次中最小值的循环次数))。
一个程序是一个一个的处理,一个程序是一批一批的处理,这是问题的关键。(再就是处理过程中进行速度会加快,因为每循环一次被判断的数量只减不增)。

素数问题的解决是我学习编程永恒的动力。
2021-09-14 12:13
快速回复:用删除法编写一个制作素数表的vfp程序
数据加载中...
 
   



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

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