Number of Positive Factors Question

Question

Hello, I was trying to figure out if the number 4294967297 was prime or composite. I figured out the answer is composite and that it is divisible by 641, but it took me longer to figure out than I would prefer. I was wondering if anyone could help me with a faster way other than taking the square root of the number, getting an answer, and then dividing the original number by primes less than that square root. Thanks a lot.

-Pipi

Answer 1

Given your algorithm, it should have taken you only a couple of seconds to get the result that you have (for example, you can do this in Excel). You will easily see that 641 is the only factor between 2 and 65536, which means that the only other factor the number that you are factoring divided by 641.

The even quicker way: do an internet search of your number and you will get this result.

That 65536 = 2^16 may pique your interest. Your target number equals 2^32+1; numbers of the form 2^(2^n)+1 are known as Fermat numbers.

n = 5 generates the first composite Fermat number, but no Fermat number for n > 5 has been proven to be prime (5-32 along with certain others have been shown to be composite).