素数定义：
该数只能被1和它本身整除（1不是素数）
解法不断优化版：
- 定义一个函数判断是否是素数
- 判断函数的优化，循环只需要从[2,sqrt(n))即可。
- 使用排除法的思想，2是素数 2的整数倍（2倍以上）不是素数；3是素数，3的整数倍不是素数 等等
- 再上述方法再加上循环的优化，循环只需要从[2,sqrt(n))即可。
代码如下
package general_tips;
import java.util.Arrays;
public class CountPrimes {
public static void main(String[] args) {
CountPrimes c = new CountPrimes();
System.out.println( c.countPrime(100));
System.out.println( c.countPrime1(100));
System.out.println( c.countPrime2(100));
}
/**
* 原始方法，先定义一个函数判断是否是素数，然后再循环统计
* @param n
* @return
*/
public int countPrime(int n){
int count=0;
for(int i=0;i<=n;i++){
if(isPrime(i)) count++;
}
return count;
}
/**
* 利用排除法的思想，判断[2,n]有几个素数
* @param n
* @return
*/
public int countPrime1(int n){
//初始化一个布尔类型的数组，将其都设置为true;
//循环遍历，将2的整数被都设置为false
//最后计数
boolean flag[]=new boolean[n+1];
Arrays.fill(flag,true);
for(int i=2;i<n+1;i++){
if(flag[i]){
for(int j=2*i;j<n+1;j+=i){
flag[j]=false;
}
}
}
int count=0;
for(int i=2;i<n+1;i++){
if(flag[i]) count++;
}
return count;
}
public int countPrime2(int n){
boolean flag[]=new boolean[n+1];
Arrays.fill(flag,true);
for(int i=2;i*i<n+1;i++){
if(flag[i]){
//前面的有些数已经置为false了，不需要重复
for(int j=i*i;j<n+1;j+=i){
flag[j]=false;
}
}
}
int count=0;
for(int i=2;i<n+1;i++){
if(flag[i]) count++;
}
return count;
}
public boolean isPrime(int n){
if(n<=1) return false;
for(int i=2;i<n;i++){
if(n%i==0) return false;
}
return true;
}
public boolean isPrime2(int n){
//比如n=12只需要判断它能否被[2,sqrt(n))之间的数整除，因为前后是对称的
if(n<=1) return false;
for(int i=2;i*i<n;i++){
if(n%i==0) return false;
}
return true;
}
}