How can I find primes multiplied by powers of two in a Python range?

0
0
Asked By MellowCedar42 On

I'm new to Python and want to write a program that accepts a positive integer range, then prints every number that is either prime or can be written as a prime multiplied by a power of two. For example, in the range 8 through 16, the results should be 8 (2×2^2), 10 (5×2), 11, 12 (3×2^2), 13, 14 (7×2), and 16 (2^4). The program should clarify whether the ending value is included and should probably print all matching numbers rather than choose just one.

3 Answers

Answered By SunnyMaple_19 On

Here is a beginner-friendly version:

```python
def is_prime(n):
if n < 2:
return False
for divisor in range(2, int(n ** 0.5) + 1):
if n % divisor == 0:
return False
return True

def is_special(n):
while n % 2 == 0:
n //= 2
return n == 1 or is_prime(n)

start = int(input("Start: "))
end = int(input("End, inclusive: "))

for number in range(start, end + 1):
if is_special(number):
print(number)
```

The `+ 1` makes the ending value inclusive. Without it, Python's `range` stops just before `end`.

Answered By QuietLemon88 On

You can also think of this as removing every factor of two and checking what remains. Bit shifting can do the same thing, but repeated integer division is much easier to understand when you’re learning. Also, 10 is 5×2^1, not 5×2^2; 8 is 2^3, and 16 is 2^4.

Answered By PixelHarbor7 On

A useful way to test this is to repeatedly divide the number by 2 while it is even. Once that is finished, the remaining value is odd. The original number has the desired form if that remaining value is 1 or a prime number. For example, 40 becomes 20, then 10, then 5, so it qualifies because 5 is prime. You can put that logic in an `is_special` function and use it while looping through the range.

Related Questions

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.