View Single Post
Old 2004-01-27, 05:07   #14
dsouza123's Avatar
Sep 2002

2·331 Posts

Some basic background information on trial factoring.

Only need to test to the square root of the number.

For numbers expressed in base ten the square root will be at most one more than half the number of digits as the number your trying to factor.

A 15 digit number would have 8 digits max for the square root.

All primes except 2 and 3 are 6x +/- 1 with x = 1 ... so the factor mod 6 must be either 1 or 5 to be a potential prime.

A 64 bit unsigned integer can hold a 20 digit number (18446744073709551615 max).
dsouza123 is offline   Reply With Quote