Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Which is faster?

Justin Porter
Ranch Hand
Posts: 34
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.

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
author
Sheriff
Posts: 14112
I'd bet on the latter, but to be sure I'd simply try both versions.

William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13074
6
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
author
Sheriff
Posts: 14112
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
Ranch Hand
Posts: 34
One other thing... roughly 10% of all integers are primes, correct?

Steven Bell
Ranch Hand
Posts: 1071
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
author
Sheriff
Posts: 14112
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?