- #1

- 8

- 0

- TL;DR Summary
- Count all integers < N that are divisible only by one power of 2

Hi,

The original problem was : for a given number k = d + n/d, where d is a divisor of another number n, how many k <= N are prime?

When I looked at this problem, for k to be prime > 2, it has to be odd.

This implies d and n/d can't both be even or odd. If d = 2, then d is even and n/d has to be odd.

Thus, n/d can't have more than one power of two.

If I can work out how to count integers <= N that only have one power of two, I can then test for primality within those integers. Any help in working this out, or if you could point out a general direction I should be looking in will be greatly appreciated.

Thanks,

The original problem was : for a given number k = d + n/d, where d is a divisor of another number n, how many k <= N are prime?

When I looked at this problem, for k to be prime > 2, it has to be odd.

This implies d and n/d can't both be even or odd. If d = 2, then d is even and n/d has to be odd.

Thus, n/d can't have more than one power of two.

If I can work out how to count integers <= N that only have one power of two, I can then test for primality within those integers. Any help in working this out, or if you could point out a general direction I should be looking in will be greatly appreciated.

Thanks,