题目地址：

https://www.lintcode.com/problem/three-distinct-factors/description

给定一个正整数$n$，判断它是否有三个不同的正因子，

首先$1$不满足，接着考虑大于$1$的数$n$。$n$必有正因子$1$和$n$，如果$n$只有三个不同因子的话，其必然是某个素数的平方。只需要判断一下这一点即可。代码如下：

public class Solution { /** * @param n: the given number * @return: return true if it has exactly three distinct factors, otherwise false */ public boolean isThreeDisctFactors(long n) { // write your code here if (n == 1) { return false; } long i = (long) Math.sqrt(n); // 如果不是完全平方数，则返回false if (i * i != n) { return false; } // 如果平方根不是素数也返回false for (long j = 2; j < Math.sqrt(i); j++) { if (i % j == 0) { return false; } } return true; } }

时间复杂度$O(\sqrt{n})$，空间$O(1)$。