count_if algorithm help

[gdogg]

I have created a program that creates n number of random numbers between 1 and x. My problem is that i have to count how many of those random numbers are prime. To do this i use the count_if algorithm. I have a template class that determines if the number is prime or not. Now, I know the is_prime template class works. I have tested serveral times by itself. But when i use it as a predicate within count_if, it fails. Does anyone have any leads for me to follow?

[Philip Nicoletti]

bool operator () for is_prime is not correct. It fails for
certain even numbers (examples : 4,82).

[Yves M]

Indeed, and checking for that would be easy. Since the typename has to be integral, you could just change it to:


bool operator() (T primer)
{
prime=primer;
if (!(prime & 1) && (prime != 2)) return false;
long double z=sqrt(static_cast<unsigned long double>(prime));
for(T i=3; i<=z;i=i+2)
{

if(gcd(i,prime)!=1)

return false;
}
cout<<"true "<<prime<<endl;
return true;
}

[gdogg]

Thanks Yves!! If i could get a little teaching...I guess i am not understanding how the line:if (!(prime & 1) && (prime != 2)) return false;

works. Mostly the (prime & 1) part. How does that catch the number 82? I have only seen single & used in references, but get the feeling its doing something else here.

[Yves M]

Yes, sorry, that's a bit obscure.

In prime & 1 the ampersand ( & ) stands for the bit-wise AND operator. This means that the result of the expression is 1 if prime is an odd integer. So the whole expression is in plain english:


IF
NOT
prime is an odd integer
AND
prime is different from 2
THEN
return false

In other words, it returns false if prime is an even integer different from 2.

[gdogg]

sweet thanks man.

[MikeAThon]

Originally posted by Yves M
In prime & 1 the ampersand ( & ) stands for the bit-wise AND operator. This means that the result of the expression is 1 if prime is an odd integer. ....
But prime is not guarenteed to be an integer; rather, it's type is "T" and therefore can be a float, double, etc. The code prime & 1 correctly differentiates between odds and evens only if prime, in fact, is an integer value. It'll fail (actually, it'll give meaningless results) for other types like float.

Incidentally, I don't think it makes any sense to determine whether a floating point value is prime since the notion of "prime-ness" only has meaning for integers. Is there some way to restrict the OP's template class so that it only has meaning for integral types, or at least checks for them? (I actually don't know if it will compile if you tried to instantiate an is_prime<float>, for example).

-Mike

[Yves M]

Passing anything else than an integral type as the typename parameter will already fail at compilation time because of the % operator used in the GCD function. So if you try passing floats you'll get a compiler error.

So prime is indeed guaranteed to be integral.


I actually don't know if it will compile if you tried to instantiate an is_prime<float>, for example

No it doesn't and it's not supposed to be anyways.

[gdogg]

There is a possible loss of data, but we are doing this to check unsigned int and unsigned long.

on another note. I am now trying to incorporate the remove_copy_if algorithm.
My problem is that im supposed to use the is_prime predicate function, but it returns true if something is prime. How do you set up remove_copy_if to remove the ones in which it returns false? Ive gone through two books and cant find an example of it, or if it can even be done. I thought the obvious logical not operator would work, but i get a syntax error.

edit: Passed a float just for fun and no errors, compiled as if nothing was wrong.

[Yves M]

I would have used unary_compose with unary_negate and isprime, but it's not in the standard C++ STL, it's only an externsion of STLPort [ the docs here (http://www.sgi.com/tech/stl/unary_compose.html) ]. I'm not sure how you would do it easily otherwise.