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? thanks
+6
A:
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!
Moron
2010-05-27 20:02:06
not very easy is an understatement :P Its the question that has bothered mathematicians since the beginning of time.
ldog
2010-05-27 20:06:19
@gmatt: Yup! :-)
Moron
2010-05-27 20:09:52
A:
No language has such an intrinsic function as far as I'm aware. There's only the brute force method of :
myNum (an integer)
if myNum mod 2 = 0 --> yes, then break, if not, continue
if myNum mod n = 0
n=n+2 (evens dealt with)
rinse, repeat
Justin
2010-05-27 20:04:35
Thank god for computational computer science and mathematics there is a faster algorithm :).
Pieter
2010-05-27 20:09:42
+1 indeed. Well, I figured anyone who would ask the question was probably after a simple solution and wasn't trying to break any records or find new primes. Certainly there are highly abstract algorithms out there, but if that's what the OP is after they probably want an advanced course in mathematics and not a quick solution on SO.
Justin
2010-05-27 20:16:52
+1
A:
For a good example of a Sieve algorithm for finding primes you can check our this wikipedia page.
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.
Shaded
2010-05-27 20:21:55
A:
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
2010-05-28 06:27:39