Which is faster?

[Justin Porter]

I'm working with a number (count) roughly 320 bits in length, and a number (big) roughly 640 bits in length. I have both of the numbers in BigInteger form.

if (count.isProbablePrime(100))
if (big.mod(count).equals(zero))

Now is it faster to check if 'count' is probably prime (maybe with a lower certainty parameter than 100), and then if it is, see if it is a factor of 'big', or would it just be faster to check if it is a factor of 'big' for each of them? Any comments would be appreciated, thanks!

[Ilja Preuss]

I'd bet on the latter, but to be sure I'd simply try both versions.

[William Brogden]

With primitive ints there would be some fast checks - such as rejecting numbers with low bit = 0. I am guessing you could try rejecting all BigInteger where getlowestSetBit() != 0 - that is half your possible count values right there.
Bill

[Ilja Preuss]

Originally posted by William Brogden:
With primitive ints there would be some fast checks - such as rejecting numbers with low bit = 0.

Isn't 2 a prime?

[Justin Porter]

One other thing... roughly 10% of all integers are primes, correct?

[Steven Bell]

Originally posted by Justin Porter:
One other thing... roughly 10% of all integers are primes, correct?

No, as Natural numbers get larger the percentage of primes tends towards, but never reaches, 0.

[Ilja Preuss]

Originally posted by Steven Bell:


No, as Natural numbers get larger the percentage of primes tends towards, but never reaches, 0.

That's interesting! I would have guessed that, too, but is it proven fact?