1952.三除数

1952.三除数

https://leetcode-cn.com/problems/three-divisors/

一、暴力法

遍历1~n，硬算

改进

16=2*8=8*2，即当一个数拆成a*b，若a!=b，同样会存在对称的b*a。遍历时不需要到n，只需要到$\sqrt n$即可，之后的可以用对称求出

class Solution:
    def isThree(self, n: int) -> bool:
        i = 1
        cnt = 0
        while i * i <= n:	#只需要遍历到根号n
            if n % i == 0:
                cnt += 1
                if i * i != n:	#两个因数不相等，则必然存在对称的
                    cnt += 1
            i += 1
        return cnt == 3