Puppy Linux Discussion Forum

[mahaju]

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/SimilarQuestions.do?req=binary+numbers+form+101+10101+1010101+prime

http://anjackson.net/2007/07/19/visualising_prime_numbers_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

[Jasper]

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).

[Moose On The Loose]

[Flash]

Even numbers (ending in 0, 2, 4, 6, cannot be primes, so right there you cut your work in half.

[mahaju]

I agree that even numbers cannot be prime, but this doesn't actually cut my work in half
because it only tells me about the LSB
If my number is, say, 10 bits long then I don't think it much reduces my work

[Jasper]

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

[Moose On The Loose]

[lwill]

2 IS prime

[Jasper]

Hi,

Re: the "51" conjecture above

Type into a console:

factor 2251799813685247

and you will see its prime factors are:
7 103 2143 11119 and 131071

The 51 digit binary number consisting entirely of 1's = 2^51-1 = 2,251,799,813,685,247

My regards

[bugman]

[bugman]