这段代码片段是做什么的？

Question

问题：

给定以下代码片段：

bool foo(int n) {
   for(int i=3;i<sqrt(n)+0.5;i+=2)
      {
        if((n%i)==0){
          return false;
         }
      }
   return true;
}

你能猜出函数foo的目的吗？

乍一看，似乎foo是在检查质数，但实际情况并非如此。我写了一个小测试程序，并得到了以下输出：

在1到100之间，foo返回true的数字有：

1 2 3 4 5 6 7 8 10 11 13 14 16 17 19 20 22 23 26 28 29 31 32 34 37 38 41 43 44 46 47 52 53 58 59 61 62 64 67 68 71 73 74 76 79 82 83 86 88 89 92 94 97

在1到100之间，foo返回false的数字有：

9 12 15 18 21 24 25 27 30 33 35 36 39 40 42 45 48 49 50 51 54 55 56 57 60 63 65 66 69 70 72 75 77 78 80 81 84 85 87 90 91 93 95 96 98 99 100

从这个数字序列中，我无法理解foo的作用。

- whacko__Cracko

---

@nthrgeek：为什么这个函数叫做foo？你有没有可能用反汇编器得到这个函数，所以你不知道它的名字？给我们一些上下文，否则我倾向于认为你在逆向工程一些不应该逆向工程的东西！ - jkp

@jkp：不，这是一个面试问题，要求我们回答这个函数的目的，因此取名为foo。 :) - whacko__Cracko

Answer 1

这看起来像是一个素数检查器，不考虑偶数和1，也就是说，它假定您已经丢弃了偶数和1。

如果返回true，则说明该数字是质数或一些由2的幂乘以至多一个其他质数组成的非质数。如果返回true的非质数，则是那些没有奇数质因子或其唯一的奇数质因子大于原始数的平方根的数。

查看一下列表中使n％2&& foo（n）为真的数字。

- CB Bailey

---

我认为这是最好的答案。 - Scott Evernden

如果我们放弃数字1和所有其他偶数，假设2是第一个数字（未经检查），那么才能为剩下的数字给出正确答案。 - whacko__Cracko

如果1是质数，那么数字就没有唯一的质因数分解。 - GManNickG

@ Scott Evernden ：你也可以看一下这个：http://zh.wikipedia.org/wiki/质数列表 - whacko__Cracko

我已经对描述进行了小的更新，以考虑其中一个。 - CB Bailey

Answer 2

在阅读了Charles Bailey的答案后，我认为该函数实际上是在检查具有某些限制条件的质数。

它正在检查质数，假设您已经丢弃了1和所有偶数。此外，您还必须考虑2是一个质数。

这是结论的C++程序：

#include <iostream>
#include <cmath>
#define MAX 1000

bool foo(int n) {
   for(int i=3;i<sqrt(n)+0.5;i+=2)
      {
        if((n%i)==0){
          return false;
         }
      }
    return true;

}

int isprime(int num){ /*Sieve of eratosthenes */

if(num == 1) return false;
bool Primes[MAX+1] = {0};
bool flag;

for(int i=2;i*i<=MAX;i++)
   if(Primes[i] == 0)
     for(int j=2*i;j<=MAX;j+=i)
        Primes[j] = 1;

return !Primes[num];
}

int main(void){
   int Count = 1;
   std::cout<<2<<" ";
   for(int i=2;i<=MAX;i++){
       if((i % 2) && foo(i)){std::cout<<i<<" ";
        Count++;
      }
  }
  std::cout<<"\nCount :"<<Count<<"\n\n\n";

 Count ^= Count;
 for(int i=1;i<=MAX;i++){
    if(isprime(i) == true){std::cout<<i<<" ";
    Count++;
    }
}
std::cout<<"\nCount :"<<Count<<"\n\n\n";

return 0;
}

谢谢！

- whacko__Cracko

Answer 3

如果n除了1、n和可能的2和n/2之外没有其他因数，则返回true。(编辑:正如评论所指出的那样，这不是完全正确的。新尝试：如果n没有小于或等于sqrt(n)的因数，则返回true，除了1和可能的2的幂次方。)

对我来说，它看起来像是旨在返回质数但有一个bug：它没有将2考虑为可能的因数。

- Jason Orendorff

---

关于那个 bug，是的，我的印象也是如此。没有什么比一个有问题的面试问题更糟糕的了。;^)~ - Don Wakefield

我认为问题中没有任何错误。 - whacko__Cracko

44出现在顶部列表中，它有2、4、11和22的约数，因此它不像1、n、2、n/2那样具有很高的选择性。 - CB Bailey

这不是真的。7是28的因数，但foo(28)返回true。 - recursive

Answer 4

这是一个需要Trac票证的质数算法。

- Scott Evernden

---

我的意思是它有漏洞 -- 如果更改了2个字符 [ "for(int i=3;i<sqrt(n)+0.5;i+=2)" 被编辑为 "for(int i=2;i<sqrt(n)+0.5;i+=1)" ] 它将正确地识别质数。 - Scott Evernden