What does this code-snippet do?

Question

Question:

Given the following code snippet:

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

Can you figure out what is the purpose of the function foo ?

Well,On first look it may seems that foo is checking for prime numbers but it is not the case.I wrote a small test program and got this output:

foo returns true for these numbers between 1 to 100:

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 4 6 47 52 53 58 59 61 62 64 67 68 71 73 74 76 79 82 83 86 88 89 92 94 97

foo returns false for these numbers between 1 to 100:

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

I am unable to understand what the foo is doing from the series.

Answer 1

It returns true if n has no divisors other than 1, n, and perhaps 2 and n/2. (EDIT: That isn't quite right, as the comments pointed out. New attempt: It returns true if n has no divisors less than or equal to sqrt(n) other than 1, and perhaps powers of 2.)

(To me, it looks like it was intended to return prime numbers but has a bug: it does not consider 2 as a possible divisor.)

Answer 2

It looks like a prime number checker that doesn't deal with even numbers or one, i.e. it assumes that you've already discarded even numbers and one.

The numbers for which it returns true are primes, or some non-primes that consist of powers of two multiplied by at most one other prime. The non-primes that it returns true for are those with no odd prime divisors or where the only odd prime divisor is larger than the square root of the original number.

Have a look at a list of numbers for which n % 2 && foo(n).

Answer 3

It's a prime number algorithm that needs a Trac ticket.

Answer 4

After reading at the answer from Charles Bailey,I think that function is actually checking for prime numbers with some constraints.

It is checking for prime numbers assuming that you have already discarded 1 & all the even numbers.Also you have to consider that 2 is a prime number yourself.

The C++ program for the conclusion:

#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;
}

Thanks !