Would someone mind elaborating the explanation in the manual?
cic_3_b at yahoo.com
Fri Oct 24 21:42:39 CEST 2003
In the efficiency section of the GMP manual I came across the
following couple lines
However when testing divisibility by several small integers, it's
best to take a remainder modulo their product, to save
multi-precision operations. For instance to test whether a number is
divisible by any of 23, 29 or 31 take a remainder modulo 23*29*31 =
20677 and then test that.
Needless to say I don't understand this. Does someone have either a
web site that has the formulas describing this process (also if
possible a proof) or some example code that achieves this purpose?
I have already searched google and I keep coming up with the disible
"tricks" these only show divisibility for one number. I am interested
in checking if a number is divisible by a couple small numbers (to
weed out values before I waste time doing detailed computation)
Thanks in Advance
Live with it
Do you Yahoo!?
The New Yahoo! Shopping - with improved product search
More information about the gmp-discuss