求素数的个数。递归和循环.求优化

Question

前几天看到这个题。
原贴找不到了。请大家给看看哪里有需要改进的：
package com.miracle.algorithm;/**
 * 输入a b （0<a<=b<10000000)
求a b之间（不算a,b）的素数个数！

input:
3 17
output:
4

因为之间的是5 7 11 13 * @author hyliu
 *
 */
public class PrimeNum { public static void main(String[] args) {
long begin = System.nanoTime(); System.out.println("5到41之间的素数有：" + count2(5, 100) + "个");
long end = System.nanoTime();
System.out.println(end - begin);
//额。下面的递归太大会栈溢出！10000极限了.较小的数计算会比较快。否则还是循环快
begin = System.nanoTime();
System.out.println("5到41之间的素数有：" + count(5, 100) + "个");
end = System.nanoTime();
System.out.println(end - begin);
} public static int count(int begin, int end) {
int num = 0;
for (int i = begin + 1; i < end; i++) {
num += isPrime(i - 1, i);
}
System.out.println();
return num;
} public static int count2(int begin, int end) {
int num = 0;
for (int i = begin + 1; i < end; i++) {
num += isPrime2(i);
}
System.out.println();
return num;
} public static int isPrime2(int n) {
int res = 1;
if (n == 2) {
return 1;
}
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return 0;
}
}
return res;
} public static int isPrime(int x, int n) {
if (x <= 1) {// is prime
// System.out.print(n + ",");
return 1;
}
if (n % x == 0) { //is not prime
return 0;
}
return isPrime(x - 1, n);
}}

Answer 1

isPrime2的for循环中，只需要根号n即可，不用到n
for (int i = 2; i <Math.sqrt(n); i++) {
            if (n % i == 0) {
                return 0;
            }
        }

Answer 2

for (int i = 3; i < n/2; i+2) { //大于3以后的偶数都不可能是素数了，所以判断奇数就可以

Answer 3

void prime(int a,int b)
{
int i;
int j;
bool k;
for(i=a;i<b;i++)
{
for(j=2;j<i;j++)
{
if(i%j==0)
{
k=false;
break;
}
else
{
k=true;
}
}
if(!k)
{
continue; 
}
System.out.println(i);
}
}

Answer 4

这个可是好思路，省空间可以这样
第从1开始到n的素数和为An,然后根据上面找出通项公式An,n在范围（start,end）区间内有效
建立多个An，可以把1-n的素数个数固定

Answer 5

刚才试了一下，这里是小于等于，呵呵
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return 0;
}
}

Answer 6

    public static void main(String[] args) {
        System.out.println(ssu(2, 120000000));
    }    public static int ssu(int f, int e) {
        if (f < 2 || e < 2) {
            return 0;
        }
        int max = Math.max(f, e);
        int min = Math.min(f, e);
        //要查找的区间
        boolean[] d = new boolean[max];
        //开始找的数
        long s = System.nanoTime();
        for (int i = 2; i < max; i++) {
            int j = i;
            //如果还没被查找过，例如查找过2后，4，6，8...不用再找
            if (!d[j] && j < max) {
                //查找
                for (j += i; j < max; j += i) {
                    d[j] = true;
                }
            }
        }
        System.out.println((System.nanoTime() - s));
        int sum = 0;
        for (int i = min + 1; i < max; i++) {
            if (!d[i - min]) {
                sum++;
            }
        }
        return sum;
    }