确定素性

Question

put "enter a number to determine if it is or is not prime"
get primenum
% for i : 1 .. primenum by 1
% end for
if (primenum / primenum) = 1 or primenum / 1 = 0 then
    put primenum, " is a prime number"
else
    put primenum, " is not a prime number"
end if

输出说12是素数,这是错误的.我该如何修复此代码？

Answer 1

好吧,我不知道那种语言,但它看起来相当容易阅读.你的第一个问题是这一行:

if (primenum / primenum) = 1 or primenum / 1 = 0 then

这是测试以查看primenum除以primenum1是否或primenum除以1是零.第一个条件将始终为true,因此您的算法将报告每个整数都是素数.

让我们回想一下素数的定义.如果自然数n具有两个不同的自然数除数,则自然数是素数.这意味着要检查并查看是否n为素数,您必须验证n除了1和n它本身之外没有其他除数(注意,隐含地n不能等于1否则它的唯一除数是1,1并且它们不是不同的).要做到这一点,只需考虑所有可能的数字,这些数字可能是n排除1和n自身的除数,并检查它们是否有任何区别n.这意味着,我们刚刚从循环2到n - 1检查,如果这些数字的平均分配n.该范围内的自然数2到n - 1有可能失效的唯一可能的数字n被素数.

因此,实现关于数字是否为素数的测试的最天真的方式如下.接受输入数字n.然后,检查是否n小于2.如果是,它不能是素数.然后,从循环2到n - 1; 调用循环变量k.检查,看是否有k在2以n - 1整除n(if n mod k = 0).如果有这样的话k,那么n就不能成为素数而你可以从循环中脱离出来.否则,如果循环终止而没有破坏n则为素数.所以,在伪代码中

integer n
get n
boolean flag
if n < 2
    flag = false
else
    flag = true
    for k = 2 to n - 1
        if n mod k = 0 
            flag = false
            break
if flag
    print "prime"
else
    print "not prime"

现在,只有一个关于您的代码的小评论.不要命名输入primenum.您的代码的读者可能会认为这primenum实际上是一个素数,因为您将其命名为.这里的名字valueToTest会非常受欢迎.