1

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?

Nifle
  • 11,745
  • 10
  • 75
  • 100
  • 1
    This isn't really a programming question. – David Thornley May 27 '10 at 20:02
  • 2
    @David Thornley: Determining if a number is primes appears in real-world programming problems. I think he is asking if there is some way to determine if a number is prime using bitwise operations. – Mark Byers May 27 '10 at 20:05

5 Answers5

6

Detecting if a number is prime is not very easy!

Read this article about the PRIMES is in P breakthrough: http://www.ams.org/notices/200305/fea-bornemann.pdf to give you an idea of how tough a problem this actually is.

This news article might be an easier read: http://members.cox.net/mathmistakes/primes.htm

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

  • 1
    not very easy is an understatement :P Its the question that has bothered mathematicians since the beginning of time. – ldog May 27 '10 at 20:06
5

Generally you just check.

genpfault
  • 51,148
  • 11
  • 85
  • 139
1

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

Sieve of Eratosthenes

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.

Ben Blank
  • 54,908
  • 28
  • 127
  • 156
Shaded
  • 17,276
  • 8
  • 37
  • 62
0
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.

Toomtarm Kung
  • 594
  • 2
  • 7
  • 11
0

There is really big difference between decting power of 2 and prime numbers.
If you'll look at our system of number representation: 1243 = 1*103 + 2*102 + 4*101 + 3*100
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).
The same for binary: 1243 = 1*210 + 0*29 + 0*28 + 1*27 + 1*26 + 0*25 + 1*24 + 1*23 + 0*22 + 1*21 + 1*20
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 = 20 * 30 * 50 * 70 * 111 * 130 * 170 * 190 * 230 * 290 * 310 * 370 * 410 * 430 * 470 * 530 * 590 * 610 * 670 * 710 * 730 * 790 * 830 * 890 * 970 * 1010 * 1030 * 1070 * 1090 * 1131 = 111 * 1131 = [0,0,0,0,1,0,0,0,0,0...]prime-based
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.

ony
  • 12,457
  • 1
  • 33
  • 41