I am trying to solve the problem 'Power of Two' on Leetcode.

我正在尝试解决Leetcode上的“Power of Two”问题。

My idea is that for n>=2 to be a power of two, two must divide n and n must not be divisible by any prime 2<= p<= sqrt(n). So first check if n is divisible by two, if not, then it isn't a power of two. If it is divisible, find the primes 2<= p<= sqrt(n) and check if any of them divide n, if at least one does, it isn't a power of two, if none do then n is a power of two.

我的想法是，对于n>=2的幂，2必须除以n，并且n不能被任何素数2<=p<=SQRT(N)整除。所以首先检查n是否可以被2整除，如果不是，那么它不是2的幂。如果它是整除的，找出素数2<=p<=Sqrt(N)，并检查它们中是否有任何一个除以n，如果至少有一个除以n，则它不是2的幂，如果没有，则n是2的幂。

This was my code.

这是我的密码。

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 1:
            return True
        else:
            if n % 2 != 0:
                return False
            else:
                for i in range(3, round(math.sqrt(n)) + 1):
                    for j in range(2, round(math.sqrt(i)) + 1):
                        if i % j == 0:
                            break
                        else:
                            continue
                    if n % i == 0:
                        return False
                    else:
                        continue
                return True

I understand this is most likely not the most effective way to solve this problem but I'd like to understand where my code has gone wrong. For example, n = 16 returns False when it should return True.

我知道这很可能不是解决这个问题的最有效的方法，但我想知道我的代码哪里出了问题。例如，n=16返回False，而它应该返回True。

@Chris nicely explained the issues with you code.

@Chris很好地解释了您的代码的问题。

If you want another approach you can use binary logic:

如果您想要另一种方法，可以使用二进制逻辑：

def isPowerOfTwo(n):
    return n > 0 and (n & (n-1) == 0)

for i in range(100000):
    if isPowerOfTwo(i):
        print(i, end=' ')

Output:

产出：

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536

How does it work?

A power of 2 as binary number is represented by a single 1 and the rest as 0s. Subtracting 1 will necessary produce a number which won't have 1 on the same bit, thus the boolean & will give 0.

作为二进制数的2的幂由单个1表示，其余的表示为0。减去1将产生一个在同一位上不会有1的数字，因此布尔值&将得到0。

Example:

示例：

# 16    00010000
# 15    00001111
# 16&15 00000000 -> 0

# 18    00010010
# 17    00010001
# 18&17 00010000 -> not 0

If we follow a sample of running your function:

如果我们按照运行您的函数的示例进行操作：

isPowerOfTwo(32)

32 isn't 1 and it is divisible evenly by 2, so we get to the second else branch. Rounding the square root of 32 gives us 6, so we iterate with i being from 3 to 6. Within that loop we have another loop, but it doesn't really do anything except either break out of itself or continue.

32不是1，它可以被2整除，所以我们得到了第二个Else分支。舍入32的平方根得到6，所以我们迭代的i是从3到6。在那个循环中我们有另一个循环，但它实际上不做任何事情，除了脱离自己或继续。

We then test of our input number is evenly divisible by i. Since our range will include 4, and 32 is evenly divisible by 4, the function erroneously returns False.

然后，我们测试我们的输入数是否可以被i整除。因为我们的范围将包括4，而32可以被4整除，所以该函数错误地返回FALSE。

Your issue lies in thinking that the break and continue will affect the outer loop.

您的问题在于认为Break和Continue会影响外部循环。

You could modify your existing approach by breaking the check to determine if a number is a prime¹ out into a separate function.

您可以修改现有的方法，方法是打破检查以确定某个数字是否为素数1，并将其转换为单独的函数。

A Simpler Approach

I would suggest a simpler way of thinking about this problem.

我建议用一种更简单的方式来思考这个问题。

You're correct in that 1 is a power of everything. If the number isn't 1, then while it's larger than the base, check if it's evenly divisible by the base. If not, obviously it can't be a power of the base and we can immediately return false.

你说的对，1是万能的。如果数字不是1，那么当它大于基数时，检查它是否能被基数整除。如果不是，显然它不能是基地的异能，我们可以立即返回FALSE。

Otherwise, divide the number by the base.

否则，将数字除以基数。

Continue this until the number is not greater than the base. If at the end, the number is equal to the base, it is a power of that base.

继续执行此操作，直到该数字不大于基数。如果在末尾，该数等于底数，则它是该底数的幂。

is_power_of(32, 2)
32 % 2 == 0, so continue
16 % 2 == 0, so continue
 8 % 2 == 0, so continue
 4 % 2 == 0, so continue
 2 % 2 == 0, and the loop ends
2 == 2, so return True

is_power_of(28, 2)
28 % 2 == 0, so continue
14 % 2 == 0, so continue
 7 % 2 != 0, so return False

>>> def is_power_of(n, b):
...   if n == 1: return True
...   while n > b: 
...     if n % b != 0: return False
...     n //= b
...   return n == b
... 
>>> is_power_of(16, 2)
True
>>> is_power_of(17, 2)
False
>>> is_power_of(32, 2)
True
>>> is_power_of(28, 2)
False
>>> is_power_of(27, 3)
True

¹ If you are going to use primes, You should investigate the Sieve of Eratosthenes.

1如果你要使用素数，你应该研究埃拉托色尼的筛子。

Your loops are not quite right. Running your code returns the following list of numbers:

你的环路不太对。运行您的代码将返回以下数字列表：

1 2 4 6 8 10 14 ...

If we consider the first incorrect value, what does your outer loop do?

如果我们考虑第一个不正确的值，您的外部循环会做什么？

>>> range(3, round(math.sqrt(6)) + 1)
range(3, 3)

This will immediately cause the outer loop to break and the function returns True.

这将立即导致外部循环中断，函数返回True。

An alternative solution is to use logarithms:

另一种解决方案是使用对数：

import math

def isPowerOfTwo(n):
    if n == 0: return False
    f = math.log(n) / math.log(2)
    return f == int(f)