3 ms·
This just seems like an expansion of prime numbers to includes factors in the 2^33+ range. Basically you're calculating if a number is prime but stopping the c
by jandrese 4mo ago
This just seems like an expansion of prime numbers to includes factors in the 2^33+ range. Basically you're calculating if a number is prime but stopping the check when the factors go above 2^32.
- Taek 4mo agoWell, technically yes, but 'stopping the factors at 32 bits' is a plenty interesting constraint because it excludes all 64 bit composite numbers that have at least one factor above 2^32. You have to redo the math to make the constraint work.
- intuitionist 4mo agoHaving a prime factor greater than 2^32 accounts for about 80% of the 64-bit integers that can’t be expressed as a product of 32-bit integers. But it’s not the only way; you can also have three prime factors in the range (2^16, 2^32), for instance.
- bonzini 4mo agoMore precisely one in the range (a,2^32) and two in the range (2^32/a, 2^32). But if the latter have many duplicate prime factors it's worse.