Leetcode 204. 计数质数 java题解

https://leetcode.cn/problems/count-primes/description/

法一

class Solution {public int countPrimes(int n) {int count=0;for(int i=2;i<n;i++){//判断i是否质数boolean f=true;for(int j=1;j*j<=i;j++){//因子if(j!=1&&j!=i&&(i%j==0)){f=false;break;}}if(f){count++;}}return count;}
}
//质数：因子只有1和自己

会超时

法二：埃氏筛

数学方法
想象有一个数x，他是质数，但是他的倍数2x,…,kx（x是他的一个因子）一定不是质数。可以对这些倍数进行标记，标记为非质数，后续不再进行判断。
对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x⋅x 开始标记，因为 2x,3*x,… 这些数一定在之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。
比如(x-1)x，必然已经被(x-1)标记过所有的倍数，因为x-1排在x之前遍历到。
所以对于x的倍数遍历，应该从xx开始。

class Solution {public int countPrimes(int n) {int[] nums=new int[n];//0是，1不是int count=0;for(int i=2;i<n;i++){if(nums[i]==0){//是质数count++;//这里必须类型转换if((long)i*i<n){//i平方还在范围内for(int j=i*i;j<n;j=j+i){nums[j]=1;//非 质数}}}}return count;}
}