programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# 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: 13078
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?