Given an integer n
, return true
if n
has exactly three positive divisors. Otherwise, return false
.
An integer m
is a divisor of n
if there exists an integer k
such that n = k * m
.
Example 1:
Input: n = 2 Output: false Explantion: 2 has only two divisors: 1 and 2.
Example 2:
Input: n = 4 Output: true Explantion: 4 has three divisors: 1, 2, and 4.
Constraints:
1 <= n <= 104
Solution: Enumerate divisors.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua class Solution { public: bool isThree(int n) { int c = 0; for (int i = 1; i <= n; ++i) if (n % i == 0) ++c; return c == 3; } }; |
Optimization
Only need to enumerate divisors up to sqrt(n). Special handle for the d * d == n case.
Time complexity: O(sqrt(n))
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: bool isThree(int n) { int c = 0; for (int i = 1; i <= sqrt(n); ++i) if (n % i == 0) c += 1 + (i * i != n); return c == 3; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment