programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Devaka Cooray
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Jeanne Boyarsky
• Tim Cooke
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Tim Moores
• Mikalai Zaikin
• Carey Brown
Bartenders:

# Which is faster?

Ranch Hand
Posts: 34
• Number of slices to send:
Optional 'thank-you' note:
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!

author
Posts: 14112
• Number of slices to send:
Optional 'thank-you' note:
I'd bet on the latter, but to be sure I'd simply try both versions.

Author and all-around good cowpoke
Posts: 13078
6
• Number of slices to send:
Optional 'thank-you' note:
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
Posts: 14112
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
One other thing... roughly 10% of all integers are primes, correct?

Ranch Hand
Posts: 1071
• Number of slices to send:
Optional 'thank-you' note:

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
Posts: 14112
• Number of slices to send:
Optional 'thank-you' note:

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?

 Proudly marching to the beat of a different kettle of fish... while reading this tiny ad a bit of art, as a gift, that will fit in a stocking https://gardener-gift.com