Binary representtion of prime numbers
Binary representtion of prime numbers
Is there any way to check whether a number is prime from it's binary representation? And I do not mean the classical method of dividing the number n by numbers from 2 to n-1, but actually determining if it is a prime from it's patterns of 0's and 1's.
Here are some of the related things I have found
http://askville.amazon.com/SimilarQuest ... 0101+prime
http://anjackson.net/2007/07/19/visuali ... _in_binary
If there is any such method I would like to write a program in C or C++ to determine if a number is prime by using it's binary representation
Thanks in advance
Here are some of the related things I have found
http://askville.amazon.com/SimilarQuest ... 0101+prime
http://anjackson.net/2007/07/19/visuali ... _in_binary
If there is any such method I would like to write a program in C or C++ to determine if a number is prime by using it's binary representation
Thanks in advance
Hi,
Categorically not.
Type:
factor x
into your console/terminal where x can be any positive integer (though I don't know how large) to factorize x.
The largest known prime has almost 13,000,000 decimal digits. Note that the number 13,000,000 has only 8 decimal digits.
The natural log of that number is almost 30,000,000 which means that is the average distance between the primes.
My regards
PS It is only necessary to test to the square root of n (not n-1 and since 2 is the only even prime number it is only necessary to test odd integers).
Categorically not.
Type:
factor x
into your console/terminal where x can be any positive integer (though I don't know how large) to factorize x.
The largest known prime has almost 13,000,000 decimal digits. Note that the number 13,000,000 has only 8 decimal digits.
The natural log of that number is almost 30,000,000 which means that is the average distance between the primes.
My regards
PS It is only necessary to test to the square root of n (not n-1 and since 2 is the only even prime number it is only necessary to test odd integers).
- Moose On The Loose
- Posts: 965
- Joined: Thu 24 Feb 2011, 14:54
Re: Binary representtion of prime numbers
For speed you need a quantum computer.mahaju wrote:Is there any way to check whether a number is prime from it's binary representation? And I do not mean the classical method of dividing the number n by numbers from 2 to n-1, but actually determining if it is a prime from it's patterns of 0's and 1's.
Here are some of the related things I have found
http://askville.amazon.com/SimilarQuest ... 0101+prime
http://anjackson.net/2007/07/19/visuali ... _in_binary
If there is any such method I would like to write a program in C or C++ to determine if a number is prime by using it's binary representation
Thanks in advance
Finding out whether or not a number is prime can be done a lot faster than the trial and error divide method but the amount it is faster by is a nearly constant factor so for really big values it only takes twice the life of the universe instead of 3 times.
If you are limited to a 32 bit value, life gets a lot easier. You only need to remember the primes from 1 to 65536 and try them against your number under test. This can be quick.
Hi again,
There are types of primes with special characteristics e.g. Fermat primes of which only 5 are known and Mersenne primes of which only some 50 are known.
There are classic theorems e.g, The Prime Number Theorem and Proth's Theorem and The Proof of the Infinity of the Primes attributed to Euclid which is brilliant but simple.
For an exercise in computer programming the Sieve of Eratosthenes would take very few lines of code. 22 short lines from memory when I wrote a program in GWBasic some 30 years ago - the principle is simple.
My regards
There are types of primes with special characteristics e.g. Fermat primes of which only 5 are known and Mersenne primes of which only some 50 are known.
There are classic theorems e.g, The Prime Number Theorem and Proth's Theorem and The Proof of the Infinity of the Primes attributed to Euclid which is brilliant but simple.
For an exercise in computer programming the Sieve of Eratosthenes would take very few lines of code. 22 short lines from memory when I wrote a program in GWBasic some 30 years ago - the principle is simple.
My regards
- Moose On The Loose
- Posts: 965
- Joined: Thu 24 Feb 2011, 14:54