有图小站

关注电脑网络,记录健康生活。有图小站,价值分享。

当前位置: 首页 > 程序设计 > 质数问题,求任意数之间的质数

质数问题,求任意数之间的质数

质数,古老而又常见的数学问题,和圆周率黄金分隔一样都是数学上最为经典的问题,这些数字都被认为包含着很多有待被发现的秘密。

有不少读中学的朋友还专门查100以内的质数表,也许你会知道2、3、5、7、11,但你却未必知道1000-10000内有那些质数,或者说问你任意一个数是质数,你会判断吗。通过下面的小程序可以轻松做到。

今天有图和大家一起解决两个问题:

1、如何判断一个数是否是质数;
2、如何找出任意两个数之间的质数;

对于这个问题,我们首先要知道素数的定义:

什么是质数?质数是只有1和它本身两个约数的自然数。或者通俗的讲,质数只能被1和他本身整除,不能被任何其他的自然数整除。

举例:2、3、5、7、11、13、17、19、23、29、31、37、41……

这些数的只能被1和它自己整除。

所以,我们可以设定一下程序:

cls
input "shu ru shu zi";n

for i=2 to n-1
if n mod i=0 then
print n;"bu shi zhi shu"
end
end if
next
print n;"shi zhi shu"
end

分析一下:

判断一个数字,默认我们将判断任意数字,那么可以使用键盘输入语句 input;

第二句,为什么不是 for i=1 to n?我们已经知道1和n是任意数的约数,我们需要判断的是这个数是否还有其他的约数,所以抛开1和它本身,所以从2开始到n-1;

if语句中的mod是求余数,如 a=5 mod 3 那么a=2,10 mod 4 的结果是2,那么我们使用if n mod i=0 就可以判断,n是否可以被i整除,如果整除那么说明i是n的约数,那么n就不是质数了,所以紧接着我们就要输出,因为一旦有一个非1和n的约数,都说明它已经不是质数,所以我们就不用再往下计算了,所以需要一个end来结束整个程序。

可是我们并不知道i到什么时候结束,所以要一直判断下去,所以在if语句结束之后需要next;

如果经过所有的判断都没有print "bu shi zhi shu" 那么从2到n-1 都不是n的约数,那么说明n是质数,所以直接print n是质数。

程序分析道这里,我们回头再看程序,惊奇的发现怎么会出现两个end,这是个不规范的程序,所以我们修改、

我们可以设定一个变量,用这个变量来记录n是否被整除过,如果被整除过,这个变量做一个变化,最后来判断这个变量是否变化,来决定n是否被整除过,也就知道了n是否指质数了。

我们设定一个变量为X,那么程序可以参考这样:

cls
cls
input "shu ru shu zi";n
x=0
for i=2 to n-1
if n mod i=0 then then x=1
next
if x=1 then print n;"bu shi  zhi shu" else print n;"shi zhi shu"
end

经过一个变量记录,我们发现程序简化并且也不难理解。

但是我们需要做一些工作——优化这个程序。我们可以考虑在循环的次数上是否可以减少。根据考虑是可以减少的,那么减少多少呢?

只需要从2到n/2就可以了,为什么?假定一个数字是21,那么我们只需要判断从2开始到10.5之间的自然数是否能被整除即可,为什么呢?因为当21除以超过一半的自然数如11时,一定是小于2的,并且是1点多,显然商不是整数,所以,我们只需要判断到n/2即可。

那么程序可以改成:

cls
input "shu ru shu zi";n
x=0
for i=2 to n/2
if n mod i=0 then then x=1
next
if x=1 then print n;"bu shi  zhi shu" else print n;"shi zhi shu"
end

质数判断

质数判断

知道了如何判断一个数是否是质数,那么在一个区间内寻找质数就好办了,就是将区间内所有的自然数列举了来判断。

cls
input "a,b";a,b
for n=a to b

x=0
for i=2 to n/2
if n mod i=0 then then x=1
next i
if x=0 then print n;
next n
end

那么可以将a,b之内的所有质数列举出来,注意看最后一句 if x=0 then print n; 这句就是输出指数的,因为经过判断没有发现x变化,说明一直没有整除的现象发生。

事情还没有玩,同样,我们需要小心的是a,b的大小问题和a,b是否是整数的问题,因为,如果大家输入 10,2,不会有一个结果,因为压根儿就没进循环进行判断,如果输入一个小数开头,如2.1,10,那么会出现一连串小数,3.1,4.1,5.1……这是错误的。

所以我们要修正程序,使其更完备:

cls
input "a,b";a,b
if a>b then
t=a
a=b
b=t
end if
if int(a)<>a then a=int(a)+1
if a<2 then a=2
b=int(b)

for n=a to b
x=0
for i=2 to n/2
if n mod i=0 then then x=1
next i
if x=0 then print n;
next n
end

整个相对完备的程序可以分成一下这几块:

接受输入数据;
判断数据的大小关系,强制将小的放在前面,大的放在后面;
判断,如果a不是整数,那么取整数之后要加1;如求2.1到10之间的质数,int(2.1)的结果是2,我们显然不能从2开始判断,因为从2.1开始是大于2的所以要从3开始;
判断如果较小的数字小于2,我们一定要从2开始判断。

质数判断

质数判断

此题还有修改之处,就是我们输入的数字独立成行的解决办法,你可以在end之间加入一个空 print即可,方法就是

print

给大家留一个更有意思的作业:

证明哥德巴赫猜想:任何一个合数都可以有两个质数之和组成。

解题思路:

第一步要判断此数是否是合数;(这个非常重要,如果是一个质数的话,我们的程序做的就是无用功了)
第二步从2开始寻找一个质数,并使其满足给出的合数和这个质数之差也为质数即可,如果找到了,输出这两个质数;

自己试试吧。

今天我们介绍了质数这个古老的数学问题,你是否对循环判断语句的使用更加有感觉了呢?更多的qbasic教程参考这里

本文是 有图小站 原创,原地址 http://www.utosee.com/post/475.html 转载请保留。





上一篇:黄金分割点的计算
下一篇:很简单很实用的养生之道




版权所有 有图小站 关注 电脑 网络 软件 健康 豫ICP备12023314号