VB常用算法（三）素数

1.算法描述
质数(Prime number):是大于等于2的整数，只能被1和自身整除，不能被其他整数整除。

判断一个数m是否为素数的经典算法是:

对于m，依次从I = 2，3，4，…，m-1判断是否能被I整除。只要有一个能被I整除，m就不是素数，否则m就是素数。

Boolean类型的私有函数sushu(ByVal n为Long)

[br/]Dim I As Long

对于i = 2到n - 1

如果(n Mod i) = 0，则退出

接下来我

如果I=n，则sushu=True

结束函数

显然，事实上，我们可以改进上述内容

对于i = 2到n–1

是:

For i = 2 To int(sqr(m))

这样可以提高效率。

以上判断是否质数的代码一定要背！

应用程序示例

求100-200内的质数。

私有子命令1_Click()

Dim j为整数

对于j = 100到200

如果sushu(j) = True，则

打印j

结束If

下一个j

结束Sub

解决问题的技巧

记忆判断素数的算法过程可以根据题意灵活调用！

示例描述

编程问题(2002年春季试卷04)

求10000以内所有可以表示为两个平方之和的质数。

创意:

首先，找出10000以内的所有质数。对于每一个素数，判断它是否可以表示为两个平方的和(即对于任何比素数shu小的数I，如果I和Shu-I都是平方，就意味着它可以表示为两个平方的和。)

判断数I是否平方的方法:sqr(i)=int(sqr(i))

私有子命令1_Click()

Dim j为整数

Dim m一样长，n一样长

对于j = 2到10000

如果sushu(j) = True，则

如果pf(j，m，n) = True，则

列表1。AddItem j & "=" & m & "+" & n

结束If

结束If

下一个j

结束Sub

私有函数pf(ByVal shu为Long，m为Long，n为Long)为Boolean

[br/]Dim I As Long

对于i = 1到shu - 1

If(Sqr(I)= Int(Sqr(I)))And(Sqr(Shu-I)= Int(Sqr(Shu-I)))那么

pf = True

m = i

n = shu - i

退出功能

结束If

下一个

结束函数

2。实践练习

1)补充规范(2002年春2 (7))

下面这个程序的作用是寻找四位正整数中的超级素数。超级素数的定义是:当一个素数从较低的位置移到较高的位置后，仍是一个素数时，这个数就是超级素数。如2333，233，23和2都是质数，所以2333是超级质数。

选项显式

私有子命令1_Click()

Dim I为整数，flg为布尔值

对于I = 1001到9999，步骤2

调用sup_prime(I，flg)

如果flg Then

调试。打印I

结束If

接下来我

结束Sub

Private Sub sup_prime( (1)，F为布尔值)

Dim p As Integer

F = True

当N > 0时执行

If prime(N) Then

(2)

其他

(3)

退出Sub

结束If

循环

结束Sub

Public Function prime(p为整数)为布尔值

Dim k为整数

如果p = 1那么

退出功能

其他

对于k = 2到Sqr(p)

如果p Mod k = 0，则退出函数

下一个k

(4)

结束If

结束函数

2)编程题(2004年春季试卷03)

随机产生15个两位数的正整数，从中找出所有的素数，并记下是哪个数，然后找出其中的素数并给出其位置。