第一种：双重for循环 使除数与被除数个个计算，效率极低
代码语言：javascript复制public void test1(int n){
long start = System.currentTimeMillis(); //取开始时间
int num=0;
boolean sign;
for(int i=2;i<n;i ){
if(i % 2 == 0 && i != 2 ) continue; //偶数和1排除
sign=true;
for (int j=2;j<i;j ){
if(i%j==0){
sign=false;
break;
}
}
if (sign){
num ;
/* System.out.println("" i);*/
}
}
System.out.println(n "以内的素数有" num "个");
long end = System.currentTimeMillis();
System.out.println("The time cost is " (end - start));
System.out.println("");
}第二种：主要考虑2 ~ i/2之间的数 ，效率比第一种提高一半
代码语言：javascript复制public void test2(int n){
long start = System.currentTimeMillis(); //取开始时间
int num=0;
int j;
boolean sgin;
for (int i = 2; i <= n; i ) {
if(i % 2 == 0 && i != 2 ) continue; //偶数和1排除
sgin = true;
for (j = 2; j <= i/2 ; j ) {
if (i % j == 0) {
sgin= false;
break;
}
}
//打印
if (sgin) {
num ;
/* System.out.println("" i);*/
}
}
System.out.println(n "以内的素数有" num "个");
long end = System.currentTimeMillis();
System.out.println("The time cost is " (end - start));
System.out.println("");
}第三种：使用开方去过滤 Math.sqrt(i)
代码语言：javascript复制public void test3(int n){
long start = System.currentTimeMillis(); //取开始时间
int num=0;
int j;
boolean sgin;
for (int i = 2; i <= n; i ) {
if(i % 2 == 0 && i != 2 ) continue; //偶数和1排除
sgin= true;
for (j = 2; j <= Math.sqrt(i) ; j ) {
if (i % j == 0) {
sgin = false;
break;
}
}
//打印
if (sgin) {
num ;
/* System.out.println("" i);*/
}
}
System.out.println(n "以内的素数有" num "个");
long end = System.currentTimeMillis();
System.out.println("The time cost is " (end - start));
System.out.println("");
}第四种：逆向思维筛选质素，最为高效
代码语言：javascript复制 public void test4(int n){
long start = System.currentTimeMillis(); //取开始时间
//素数总和
int sum = 0;
//1000万以内的所有素数
//用数组将1000万以内的数分为两大派系，素数用0代替数值，合数用1代替数值；
//一开始默认全部为素数，所以值全部为0，等到开始筛选的时候再把为合数的赋值为1
int num[] = new int[n];
num[0] = 1; //由于1规定不是素数，所以要提前用1标值
//根据埃氏筛法的结论，要得到自然数 N 以内的全部素数，必须把不大于" 二次根号 N "的所有素数的倍数剔除，剩下的就是素数
double prescription = Math.sqrt(n);
for (int i = 2; i <= prescription; i ) {
//开始把所有素数的倍数剔除，剩下的就是素数
for (int j = i*i; j <= n; j =i) {
//从i*i开始去除，因为比i*i小的倍数，已经在前面去除过了
//例如：i=5
//5的2倍（10），3倍（15），在i=2的时候，已经去除过了
num[j-1] = 1; //把素数的倍数剔除，也就是赋值为1，不是素数就是合数
}
}
//遍历数组，把值为0的数全部统计出来，得到素数之和
for (int i = 0; i < num.length; i ) {
if(num[i]==0)
sum ;
}
System.out.println(n "以内的素数有" sum "个");
long end = System.currentTimeMillis();
System.out.println("The time cost is " (end - start));
System.out.println("");
}
