Question:

I know that there are many binary operations to show that something is true for example we can show if number is power of two or something else is there some theory or special binary method to show if number is prime?

Detecting if a number is prime is not very easy!

Read this article about the <a href="http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf" rel="nofollow">PRIMES is in P</a> breakthrough: <a href="http://www.ams.org/notices/200305/fea-bornemann.pdf" rel="nofollow">http://www.ams.org/notices/200305/fea-bornemann.pdf</a> to give you an idea of how tough a problem this actually is.

This news article might be an easier read: <a href="http://members.cox.net/mathmistakes/primes.htm" rel="nofollow">http://members.cox.net/mathmistakes/primes.htm</a>

In short, if you find a simple 'binary method' you will be famous!

Generally you just <a href="http://en.wikipedia.org/wiki/Primality_test" rel="nofollow">check</a>.

For a good example of a Sieve algorithm for finding primes you can check our this wikipedia page.

<a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow" title="Sieve of Eratosthenes">Sieve of Eratosthenes</a>

One of the more interesting methods for finding primes, and the Euler Sieve (touched upon at the bottom of the same page) speeds it up a little.

There is really big difference between decting power of 2 and prime numbers.<br /> If you'll look at our system of number representation: 1243 = 1*10³ + 2*10² + 4*10¹ + 3*10⁰<br /> It's pretty easy to determine when number can be divided by 10 (lowest digit is zero) or is power of 10 (all lowest digits is zero and highes it "1", or sum of all digits equals to 1).<br /> The same for binary: 1243 = 1*2¹⁰ + 0*2⁹ + 0*2⁸ + 1*2⁷ + 1*2⁶ + 0*2⁵ + 1*2⁴ + 1*2³ + 0*2² + 1*2¹ + 1*2⁰<br /> You can check digits to check if number can be divided by 2 or even is power of 2 in the same way as for 10-based number representation.

Now consider other systems of numbers representation. I guess Roman numerals should have some interesting properties also, but you probably interested in something like: 1243 = 2⁰ * 3⁰ * 5⁰ * 7⁰ * 11¹ * 13⁰ * 17⁰ * 19⁰ * 23⁰ * 29⁰ * 31⁰ * 37⁰ * 41⁰ * 43⁰ * 47⁰ * 53⁰ * 59⁰ * 61⁰ * 67⁰ * 71⁰ * 73⁰ * 79⁰ * 83⁰ * 89⁰ * 97⁰ * 101⁰ * 103⁰ * 107⁰ * 109⁰ * 113¹ = 11¹ * 113¹ = [0,0,0,0,1,0,0,0,0,0...]_prime-based<br /> I.e. number is encoded as product of powers of prime numbers. Such system have nice property of doing different prime-related checks much easier than in bits or in decimals.

P.S. While systems with weighted-sum gives you easy way to calculate sums and difference, systems with powered product simplifies multiplication and division.

bool isPrime(int number){ if(number < 2) return false; if(number == 2) return true; if(number % 2 == 0) return false; for(int i=3; (i*i)<=number; i+=2){ if(number % i == 0 ) return false; } return true; }

Notice. It will be slow if your input more than 10^9.