请教判断素数问题标题十个字

Question

rt,用语句1跟语句2判断素数有什么区别，用语句1的时候报错了，

Answer 1

如果一个数为合数，其因子一定是成对出现的。也就是说加入a是合数c的因子，则必有另一个因子b，满足a*b=c，且a≤sqrt(c) b≥sqrt(c)。

知道以上性质，我们在判断质数时就没有必要遍历到n，只需要遍历到√n即可。因为这个区间存在因子则一定是合数；这个区间不存在因子，则[√n, n)区间一定也不存在因子，故可以判断其为偶数。

用这种方法可以极大的提高判断素数的性能。你的第一种算法遍历到n，时间复杂度为O(n)；第二种算法只需要遍历到√n，时间复杂度为O(√n)。假设n=10000，第一种算法要循环10000次，而第二种算法只需要100次。性能提升是指数级的。