A27074. $下列C++代码判断一个正整数是否是质数，说法正确的是( )。bool is_prime(int n){ if(n<= 1) return false; if(n==2||n==3l|n== 5) return true; if(n%2=0ln%3==0|n%5==0) return false; int i = 7; int step =4; int finish number = sqrt(n…$

单选题困难

知识点

质数判定循环结构时间复杂度分析

题目描述

下列C++代码判断一个正整数是否是质数，说法正确的是(    )。bool is_prime(int n){ if(n<= 1) return false; if(n==2||n==3l|n== 5) return true; if(n%2=0ln%3==0|n%5==0) return false; int i = 7; int step =4; int finish number = sqrt(n)+ 1; while(i<= finish_number){ if(n%i == 0) return false; i += step; step=6-step; } return true; }

代码存在错误，比如5是质数，但因为 5 % 5 余数是0返回了 false

finish_number 的值应该是 n / 2 ，当前写法将导致错误

当前 while 循环正确的前提是：所有大于3的质数都符合 6k\pm1 形式

while 循环修改如下，其执行效果和执行时间相同。for(int i=2;i<finish_number; i++){ if(n %i == 0) return false; } return true;

上一题下一题