LeetCode204题：计数质数

这道题真的是解法很多&＃xff0c;但满足时间复杂度的还不太容易想。

解法一&＃xff1a;暴力法

外层循环从2到n&＃xff0c;内层循环从2到ni&＃xff0c;然后ni取模内层循环的值&＃xff0c;判断是否为质数。复杂度O(n2)&＃xff0c;舍弃。

解法二&＃xff1a;根据之前的质数求

思路&＃xff1a;一个数如果与比它小的所有的质数取模后结果都不为0时&＃xff0c;那么此数也是质数。所以&＃xff0c;从2开始遍历到n时&＃xff0c;每遇到一个质数就将其放到ArrayList中&＃xff08;用ArrayList而不用treeset&＃xff0c;因为不需要多余的排序操作&＃xff09;。每次判断一个数是不是质数时&＃xff0c;就遍历ArrayList进行取模比较。

虽然比较的次数少了很多了&＃xff0c;但遗憾的是依然没通过测试用例。

public static int countPrimes(int n) {if(n <3)return 0;if(n &＃61;&＃61; 3)return 1;List set&＃61;new ArrayList();set.add(2);int flag &＃61; 1;for(int i&＃61;3;i it &＃61; set.iterator();while(it.hasNext()){if(i%it.next()&＃61;&＃61;0){flag &＃61; -1;break;}}if(flag &＃61;&＃61; 1){set.add(i);}flag &＃61; 1;}return set.size();}

解法三&＃xff1a;质数折半比较

在解法二中&＃xff0c;每次都比较了比当前值小的所有质数。但观察后可以发现&＃xff0c;一个数如果与比它小的所有质数的前一半取模都不为0的话&＃xff0c;那么就没必要与后一半进行比较了&＃xff0c;因为除以小的数得到的数就是大的&＃xff0c;所有如果除小的除不尽&＃xff0c;那么除大的肯定除不尽。这样又能减少比较次数。

遗憾的是&＃xff0c;依然没通过全部的测试用例。好像是卡在1500000了。

public static int countPrimes(int n) {if(n <3)return 0;if(n &＃61;&＃61; 3)return 1;List set&＃61;new ArrayList();set.add(2);int flag &＃61; 1;for(int i&＃61;3;i it &＃61; set.iterator();int mid &＃61; set.size();int count &＃61; 0;//增加count变量用来折半while(it.hasNext()&&count<&＃61;mid/2){if(i%it.next()&＃61;&＃61;0){flag &＃61; -1;break;}count&＃43;&＃43;;}if(flag &＃61;&＃61; 1){set.add(i);}flag &＃61; 1;}return set.size();}

解法四&＃xff1a;根号n比较

解法二中采用的比较前一半的质数的方法复杂度还是不符合要求&＃xff0c;那么考虑将n取根号后取整&＃xff0c;然后再与ArrayList中小于(int)Math.sqrt(n)的质数进行取模比较&＃xff0c;思想其实与解法二是一样的&＃xff0c;都是基于除以小的数会得到大的数&＃xff0c;而一个数想要被整除并且余数大于除数的话&＃xff0c;除数最大就是sqrt(n)&＃xff0c;而解法二采用的是质数折半&＃xff0c;并不如这种精确。这样就能进一步减少比较次数。

并且&＃xff0c;这种方法通过了所有测试用例。

public static int countPrimes(int n) {if(n <3)return 0;if(n &＃61;&＃61; 3)return 1;List set&＃61;new ArrayList();set.add(2);int flag &＃61; 1;for(int i&＃61;3;i it &＃61; set.iterator();int mid &＃61; (int)Math.sqrt(n);while(it.hasNext()){int next &＃61; it.next();if(next<&＃61;mid){if(i%next&＃61;&＃61;0){flag &＃61; -1;break;}}else{break;}}if(flag &＃61;&＃61; 1){set.add(i);}flag &＃61; 1;}return set.size();}

解法五&＃xff1a;埃拉托色尼素数筛法

这种算法的思想是&＃xff0c;先假定所有的数都是质数&＃xff0c;并以布尔型数组存放&＃xff08;质数用true表示&＃xff09;。然后从2开始迭代&＃xff0c;因为默认的都是质数&＃xff0c;所以2是质数&＃xff0c;那么2的平方及2的平方&＃43;2m一定都不是质数&＃xff0c;所以把对应不是质数的元素改为false。然后迭代到3&＃xff0c;由于默认的是质数&＃xff0c;并且之前的2的循环并没有修改3为false&＃xff0c;所以3依然是质数&＃xff0c;那么同理&＃xff0c;3的平方及3的平方&＃43;3m也一定都是非质数&＃xff0c;故修改为true。以此迭代。

下面的代码是摘抄的网上的。

public static int countPrimes(int n) { //暴力算法是过不了的qwq//这个要用筛法实现boolean[] isPrime &＃61; new boolean[n];int result &＃61; 0;for (int i &＃61; 2; i

下面是n等于100000时四个方法的用时比较&＃xff08;除了第一种暴力算法&＃xff09;&＃xff1a;