怎样找素数（质数）？

Python012

怎样找素数（质数）？,第1张

拿那个数分别去除以2,3,5,7.如果都有余数则这个数一定是一个素数.以下vfp程序将计算出长度小于20位的所有素数并将其结果逐行逐列存入一个有10列的素数表中.

SELECT 1

SET ESCAPE on

USE 素数表.dbf

INSERT blank

DIMENSION a(1)

a=1

f=1

DO while a<99999999999999999999

b=MOD(a,2)

c=MOD(a,3)

d=MOD(a,5)

e=MOD(a,7)

IF b#0.and.c#0.and.d#0.and.e#0.and.a#1.or.a=2.or.a=3.or.a=5.or.a=7

DO case

CASE f=1

g="一"

CASE f=2

g="二"

CASE f=3

g="三"

CASE f=4

g="四"

CASE f=5

g="五"

CASE f=6

g="六"

CASE f=7

g="七"

CASE f=8

g="八"

CASE f=9

g="九"

CASE f=10

g="十"

ENDCASE

GO bott

command1="gather from a"+" fields "+g

&command1

f=f+1

IF f>10

f=1

INSERT blank

ENDIF

ENDIF

a=a+1

ENDDO

=messagebox("长度20位以下(含)的所有素数运算完毕！",0+64+0,"运算完成")

USE

CLOSE all

素数表.dbf结构从略.

强烈建议换黑色背景阅读，因为亮光会招虫子，黑色背景体验好 眼睛不累，体验好节能环保，体验好NO BUG 程序没有BUG

▽ 关键技能点▽

math loop algorithm

寻找素数的算法相信大家都不陌生。作为基础常用的算法之一，效率是考虑的重点。避免无谓的计算是关键，但怎么判断不必要的计算？先看一个简单栗子：

# 找出1千万以内所有能整除n的整数

分别计算三者算法的耗时

start = time.time()

**function ** # 逐一调用三种算法

end = time.time()

整除3的耗时结果：

for_loop time: 0.6796061992645264

列表推导式 time: 0.5297579765319824

slice time: 0.20990514755249023

第三种切片的效率最好，1千万以内枚举所有整除3的大致0.2秒！

耗时表现其次是列表推导式。

for循环+条件判断的耗时是切片的三倍之多！

线下课堂上将详细讲为什么会有差别？

问题难度升级：大范围内找所有素数

判断一个数是素数与否，不必从2开始逐一取余直到n-1为止，有童鞋提出只需到n//2为止即可。

其实，还可以‘犯懒’!，取余直到n的开平方取整即可。

为什么可以犯懒，只取到不到n的一半就够判断了呢？

详细见：[算法ABC-4：素数的优化算法]( http://mp.weixin.qq.com/s ?

下面算法思路2是不是已经最快的算法了？

不是，今天将介绍比较少见的第三种写法！

今天将在算法ABC-4的基础上，探讨相关的问题，在1千万以内寻找所有****非****质数 算法效率如何提高？ 先找出局部优化的两个小动作：

算法思路-1

遍历1-10000000中每一个数，isPrime(x)判断如果是素数，跳过；不是素数添加到ans列表

** Solution 1st **

** 算法思路-2****判断一个数不是素数，只要出现第一个能整除的结果立即返回True** 这样就不需要一直取余判断直到 n 0.5+1******solution 2nd ****

中阶班的逻辑训练必不可少。* 注意两种写法all()和any()的区别！

最后，第三种算法不太好理解，详细将在线下分解

算法思路-3

****solution 3rd ****

比较以下三种找素数的效率，n=100000

即找出十万以内所有的非素数需要的时间

****solution 3rd ****

结论可见，第三种方法效率是第二种的50多倍，十万以内耗时只需0.02秒，而第二种方法耗时要1秒多！

第三种写法详细讲解将在课堂讨论。