素数输出程序

Question

public class prime
{
   //一个主函数，相当于是程序的入口
   public static void main(String args[])
  {   
      long startTime = System.nanoTime();  //開始時間
        for ( int i = 2; i <=100000; i++ ) {
            int j;
            int t=1;
          for (  j = 2;j<=(int)Math.sqrt( i ); j++ )
         if ( i % j == 0 ) { t=0;  break;}
        if(t==1) System.out.print( i + " " );
      }
           
     long consumingTime = System.nanoTime() - startTime; //消耗時間
      System.out.println(consumingTime);
     System.out.println(consumingTime/1000+"微秒");
      //执行语句
      //System.out.println("hello!");
 }
}运行程序花了0.7秒，我知道这个速度很慢，不知道怎么优化让程序执行更快，谢谢大牛们的指教，谢谢，

Answer 1

求一个质数用这种方法可以，求一定范围内的质数表用筛法更快：先建一个n个元素的flag数组，初始都置为true，令i从2-根号n枚举，对每一个i，把所有索引为i的倍数的flag置为false，最后剩下的true就是质数

Answer 2

下面是一个例子，查找 100000 以内的质数，本人笔记本上耗时 38ms
思路是以存储空间换取执行效率，记录所有已经找到的质数，用于检查下一个数字是否是质数。import java.util.*;public class GetPrimes {    // 以空间换时间查找质数
    public static void main(String[] args) {        // 查找质数
        long start = System.currentTimeMillis();
        List<Integer> primes = listPrimes(100000);
        System.out.println("time: " + (System.currentTimeMillis() - start) + "ms");        // 打印查找结果
        outputPrimes(primes);
    }    private static List<Integer> listPrimes(int max) {        // 保存已经找到的质数
        LinkedList<Integer> primeList = new LinkedList<>(Arrays.asList(2, 3));        // 如果只查找 3 以内的质数，直接返回初始值
        if (max <= 3) {
            return primeList;
        }        // 3 以上的质数一定是奇数，因此 next 每次 +2，然后检查它是否是质数
        int next = primeList.getLast() + 2;        while (next < max) {
            boolean isPrime = true;            // 利用已经找到的质数来检验 next 是否是质数
            // 不需要用 primeList 中所有的数来检查，只需检查到 next 的平方根即可
            // 如果这之前的所有的质数都不能整除 next，那么 next 就是质数
            for (Integer n : primeList) {
                if (n * n > next) {
                    break;
                } else if (next % n == 0) { // 被整除了，说明不是质数
                    isPrime = false;
                }
            }            if (isPrime) {
                primeList.add(next);
            }            next = next + 2;    // 下一个要检查的数字
        }        return primeList;
    }    private static void outputPrimes(List<Integer> primes) {
        int counter = 0;
        for (Integer prime : primes) {
            System.out.print(prime + " ");
            counter++;
            if (counter % 30 == 0) {
                System.out.println();
            }
        }
    }
}

Answer 3

public class test {
public static void main(String []args){
long start=System.currentTimeMillis();
for(int i=2;i<=100000;i++){
if(isPrime(i)==1){
System.out.println(i+" ");
}
}
long end=System.currentTimeMillis();
System.out.println(end-start);



}
static int isPrime(int n){
if(n<2)
return 0;
for(int i=2;i*i<=n;i++){
if(n%i==0){
return 0;
}
}
return 1;
}
}我这是232ms，楼上是大牛