无法理解:求出1到某个数之间的素数

迷茫小一点发布于 2020-04-07 00:37， 3182 次点击

只有本站会员才能查看附件，请登录

1.假设val的输入值是100，第一次执行100%2==0，break终止for，返回false，到了2  i<=100为真，由于返回的false，2就会被当作不是素数，不会被输出，
第二次执行，由于val的输入值是100，100%3非0；，if不执行，i+1，第三次执行 100%4==0，break终止，i！=100 返回false，到2   i不就一直=2，i+1就不执行了，我这种流程的理解是否错误
2第二种理解：1 val=100   i=2   i<2 (2是val的值1~100里面的数字如：1 2 3每个数字都会进行一次判断)，此时 i<2，不成立，跳出for，执行i==val 返回true(真)，是个素数，(此时的 2 的for 是否跟1是一样的)输出一个素数，再回到1  此时在回到1 i 就永远只能i<2,  i<val是否要改成i<=val,如果是这样，那么i<=2,进入if成立 break终止，i的值回到初值i=2；此时的i==val又会返回真.....

16 回复

return_02020-04-07 09:01

为什么第8行要i==val呢

return_02020-04-07 09:07

程序代码：

bool Isprime(int val){
    for(int i=2;i<=n/2+1;i++){
        if(val%i==0)return true;
    }
    return false;
}

这样不但方便，答案也正确

迷茫小一点2020-04-07 09:50

回复 3楼 return_0

理解不了这个程序，想知道程序执行流程

wmf20142020-04-07 10:00

不要把isprime里的val和main里的val搞混，楼主提供的图片里的isprime函数没什么问题，只是判断效率不高。
1里也可以改成i<=val，反正到了需要“自己%自己”时肯定是素数了，for肯定会break，然后被“自己==自己”判断输出为true。

lin51616782020-04-07 10:13

以下是引用wmf2014在2020-4-7 10:00:43的发言：

不要把isprime里的val和main里的val搞混，楼主提供的图片里的isprime函数没什么问题，只是判断效率不高。
1里也可以改成i<=val，反正到了需要“自己%自己”时肯定是素数了，for肯定会break，然后被“自己==自己”判断输出为true。

既然你说了判断效率不高
为什么后续还提供一个判断效率更低的改动呢 ( 我都不好说改进了 )

迷茫小一点2020-04-07 10:18

我想知道我的哪种理解是正确的

迷茫小一点2020-04-07 10:22

回复 6楼 lin5161678

那个，我现在搞懵内部是如何执行的，能否讲解下嘛，谢谢

lin51616782020-04-07 10:33

以下是引用迷茫小一点在2020-4-7 10:22:31的发言：

那个，我现在搞懵内部是如何执行的，能否讲解下嘛，谢谢

你把isprime函数参数改成 value
再进行理解

[此贴子已经被作者于2020-4-7 10:38编辑过]

#10

return_02020-04-07 10:45

回复 9楼 lin5161678

???

#11

lin51616782020-04-07 11:00

以下是引用return_0在2020-4-7 10:45:24的发言：

???

发帖人把main里面的val 和 isprime的参数val 弄混了以为是一个变量
5楼的wmf2014的回复中也提到这一点
我建议他把isprime的参数改成 value
这样就不会混淆main里面的val
理解起来方便点

#12

wmf20142020-04-07 11:31

我觉得解疑答惑要切题意才算合格，就事论事嘛。
既然有人质疑我没改进，那我就给出两个改进的素数判断函数共楼主参考吧：
1，行数较少
int isprime(int n)
{
    int i;
    if(n<2)return 0;    //负数和0，1都不算质数
    for(i=2;i*i<=n&&n%i;i++);
    return i*i>n;
}
2，算术方式中判断效率较高（待检验，只是根据大于5的质数在6n两边写的）
int isprime(int n)
{
    int i;
    if(n==2||n==3||n==5)return 1;
    if(n<6)return 0;
    i=n%6;
    if(i>1&&i<5)return 0;
    for(i=7;i*i<=n&&n%i;i+=6);
    return i*i>n;
}

[此贴子已经被作者于2020-4-7 11:36编辑过]

#13

lin51616782020-04-07 11:36

以下是引用wmf2014在2020-4-7 11:31:03的发言：

我觉得解疑答惑要切题意才算合格，就事论事嘛。
既然有人质疑我没改进，那我就给出两个改进的素数判断函数共楼主参考吧：
1，行数较少
int isprime(int n)
{
    int i;
    if(n<2)return 0;    //负数和0，1都不算质数
    for(i=2;i*i<=n;i++);
    return i*i>n;
}
2，算术方式中判断效率较高（待检验，只是根据大于5的质数在6n两边写的）
int isprime(int n)
{
    int i;
    if(n==2||n==3||n==5)return 1;
    if(n<6)return 0;
    i=n%6;
    if(i>1&&i<5)return 0;
    for(i=7;i*i<=n;i+=6);
    return i*i>n;
}

都漏了整除校验
循环必然跑完

哦好吧改正了
当我没说

[此贴子已经被作者于2020-4-7 11:40编辑过]

#14

wmf20142020-04-07 11:38

回复 13楼 lin5161678

已改

#15

lin51616782020-04-07 11:41

回复 12楼 wmf2014

for(i=7;i*i<=n&&n%i;i+=6);
从7开始不停+6
6n+1 有体现了
6n-1 没找到你是怎么校验的

懂了
前面的整除判定余数是不是大于1小于5
检查n是否符合形式 6n+1 6n-1
后面的循环只是判断两种形式都统一检查

[此贴子已经被作者于2020-4-7 11:46编辑过]

#16

wmf20142020-04-07 12:07

回复 15楼 lin5161678

还是有bug的，你的疑问存在，不愿改了。

#17

wmf20142020-04-07 12:12

还是对2改下吧(已验证)：
int isprime(int n)
{
    int i, j = 4;
    if (n == 2 || n == 3 || n == 5)return 1;
    if (n < 6)return 0;
    i = n % 6;
    if (!i||(i > 1 && i < 5))return 0;
    for (i = 5; i*i <= n&& (n%i); i += j)
    {
        if (j == 4)j = 2;
        else j = 4;
    }
    return i * i > n;
}

[此贴子已经被作者于2020-4-7 13:12编辑过]