| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 10970 人关注过本帖
标题:用删除法编写一个制作素数表的vfp程序
只看楼主 加入收藏
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏(1)
得分:3 
40000000以内耗时173s,破电脑就这速度。
用数组应该可以算到超过1亿内,每个数组中元素的最大数目 一般: 2G 字节、成员数组: 2G 字节
图片附件: 游客没有浏览图片的权限,请 登录注册

程序代码:
t = SECONDS()
N = 40000000
DIMENSION arr[N,1]
arr = .T.
i = 2
DO WHILE i<=N
    FOR j=i+i TO N STEP i
        arr[j] = .F.
    ENDFOR 
    j = i+1
    DO WHILE j<=N AND !arr[j]
        j = j+1
    ENDDO
    i = j
ENDDO
CREATE CURSOR tt (bol L, num I)
INSERT INTO tt FROM ARRAY arr   
REPLACE ALL num WITH RECNO()
SELECT num FROM tt WHERE bol AND RECNO()>1 INTO TABLE 素数表
? SECONDS()-t  && N=20000000 - 87s, N=40000000 - 173s
2021-09-15 11:34
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:71
帖 子:939
专家分:683
注 册:2016-6-29
收藏
得分:0 
回复 41楼 吹水佬
t=SECONDS()
N=20000000
DIMENSION arr[N,1]
arr=.T.
i=2
DO WHILE i<=N
    FOR j=i+i TO N STEP i
    arr[j]=.F.
    ENDFOR
    j=i+1
    DO WHILE j<=N AND !arr[j]
    j=j+1
    ENDDO
    i=j
 ENDDO
 CREATE CURSOR tt(bol L,num I)
 INSERT INTO tt FROM ARRAY arr
 REPLACE ALL num WITH RECNO()
 SELECT num FROM tt WHERE bol AND RECNO()>1 INTO TABLE 素数表
 ?SECONDS()-t &&N=20000000-38.754s ,N=40000000-78.142s
我按照您的程序手工抄录了一遍。用时较少,结果存盘到:C:\program files(X86)\vfp9\素数表.dbf 中了

素数问题的解决是我学习编程永恒的动力。
2021-09-15 13:04
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
回复 42楼 独木星空
输出文件可以设置默认路径或指定路径
2021-09-15 14:35
mywisdom88
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:191
帖 子:3147
专家分:8408
注 册:2015-3-25
收藏
得分:0 
回复 41楼 吹水佬
你这是什么算法,没看到你运算,就判断了。
2021-09-15 15:33
laowan001
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:66
帖 子:1092
专家分:2686
注 册:2015-12-30
收藏
得分:0 
* 改造了31楼的程序,结果表记录1234399,用时350秒
CLEAR
CLOSE DATABASES

LOCAL kkk

SELECT 1
USE 数据源.DBF ALIAS 数据源
SELECT 2
USE 素数表.DBF ALIAS 素数表参

SELECT 5
USE 素数结果.DBF ALIAS 素数表果
DELETE ALL
PACK

SELECT 素数 数据1 FROM 素数表果 WHERE 1=2 INTO CURSOR 数据a READWRITE

kssj = DATETIME()
FOR i=1 TO 2
    SELECT 素数式+(i-1)*9699690 数据1,CAST(1 as INT) 数据mod FROM 数据源 INTO CURSOR 数据a READWRITE

    SELECT 数据a
    GO BOTTOM     &&1658880
    Kf=INT(SQRT(数据1))

    SELECT 2
    kkk = 0
    SCAN FOR RECNO()>8 AND 素数<=kf
        IF RECNO()>kkk
            WAIT TRANSFORM(RECNO()) WINDOW NOWAIT NOCLEAR
            kkk = kkk + 10
        ENDIF
        
        UPDATE 数据a SET 数据mod=MOD(数据1,素数表参.素数) WHERE 数据mod>0

        SELECT 2
    ENDSCAN
   
    INSERT INTO 素数表果 (素数) SELECT 数据1 FROM 数据a WHERE 数据mod>0
   
 ENDFOR
 USE IN 数据a
 
 MESSAGEBOX( DATETIME()-kssj)
 SELECT 素数表果
 MESSAGEBOX( RECCOUNT())
 BROWSE
 
2021-09-15 15:39
laowan001
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:66
帖 子:1092
专家分:2686
注 册:2015-12-30
收藏
得分:0 
确实没看懂吹版的程序,好像没用到数据源表和素数表,明白的给说明一下下
2021-09-15 15:43
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:71
帖 子:939
专家分:683
注 册:2016-6-29
收藏
得分:0 
回复 45楼 laowan001
首先多谢先生的回答。我还没有运行。那也比我原来的提速不少。

素数问题的解决是我学习编程永恒的动力。
2021-09-15 16:08
独木星空
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:河北省曲阳县
等 级:版主
威 望:71
帖 子:939
专家分:683
注 册:2016-6-29
收藏
得分:0 
回复 46楼 laowan001
两楼都提到吹水佬算法问题,我有点喧宾夺主了,本不该回答的,只知道大概的意思,我把程序抄写到程序中,第一次运算结果出来后,竟然连素数表也没有找到,无奈之下运行了第二次,这是出现提示信息,说那个路径之下已经存在了,是否替换,这时我才找到存放素数表的路径。
扯多了,扯远了,回到正题,他的算法就像体育课老师让学生报数那样,从开头报数,报偶数者出列(第一个报的不出列),接着报3的倍数的出列,报5的倍数出列(当然他是把它们标记为假,false,开始都标记为真,true),这样直到小于等于N为止,然后把所有标记为真的存放到素数表中(当然第一条记录排除在外,它是1)

[此贴子已经被作者于2021-9-15 16:34编辑过]


素数问题的解决是我学习编程永恒的动力。
2021-09-15 16:25
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
以下是引用mywisdom88在2021-9-15 15:33:14的发言:

你这是什么算法,没看到你运算,就判断了。

程序代码:
    筛选法求素数
    如:有10个数............ 234567891011
    先假设都是素数标记为1 .. 1111111111
    将不是素数的标记为0 .... 1101010001
    剩下标记为1的是素数 .... 23, ,5,, 7, , ,  ,11


DIMENSION arr[N,1]
arr = .T.
i = 2  筛选起始数
DO WHILE i<=N
    FOR j=i+i TO N STEP i  && 是自身倍数的不是素数
        arr[j] = .F.
    ENDFOR 
    j = i+1
    DO WHILE j<=N AND !arr[j] && 跳过连续的非素数
        j = j+1
    ENDDO
    i = j  && 下次筛选的起始数
ENDDO
2021-09-15 16:43
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
回复 48楼 独木星空
用当前PRG文件路径作为默认路径,开头加几句:
CLEAR
SET TALK OFF
SET SAFETY OFF
CLOSE TABLES ALL
cDefPath = ADDBS(JUSTPATH(SYS(16)))
SET DEFAULT TO (cDefPath)
2021-09-15 16:48
快速回复:用删除法编写一个制作素数表的vfp程序
数据加载中...
 
   



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

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