统计n以内的素数个数

素数：只能被1和自身整除的自然数，0和1除外；

举例：

输入：100        输出：25

import java.util.*;
class Test1{public static void main(String[] args){int a =100;  //输入数字// 统计素数个数int count=0;for(int i =2; i<=a; i++){int flag=0;//检查有没有被其他数字整除，如果整除，则flag=1for (int j =2; j*j<=i; j++){    //j*j<=i 其实是j<根号i,以为2*6和6*2是一样的，所以少检查一遍。if(i%j==0 ){flag = 1;break;}}//统计素数的个数if (flag !=1){count++;System.out.println(i); //查询到当前的素数为i}}System.out.println(count);  //素数的总个数}}

改进：（以空间换时间）埃氏筛选，利用合数概念来排除所有合数，剩下的都是素数。

public class Test1_1 {public static void main(String[] args){int n =100;int flag = 0;boolean[] isPrime = new boolean[n+1]; //默认都是素数for(int i=2; i<=n;i++){//这里从i开始，是避免出现算过2*4，又出现4*2for(int j=i; j*i <= n;j++){isPrime[i*j]=true;  //如果发现一个数是两数的乘积，则置为true，为合数。}}//统计素数的个数int k= 0;for(boolean i : isPrime){if(!i){flag++;System.out.println("k"+k);}k++;}//0和1除外，所以要减2;System.out.println(flag-2);}
}

结果展示：