给定1-1000000的数，快速找出质数
/* * 文件名：FindPrime .java * 版权：Copyright 2007-2017 517na Tech. Co. Ltd. All Rights Reserved. * 描述： FindPrime .java * 修改人：peiyu * 修改时间：2017年5月5日 * 修改内容：新增 */ package com.websocket.controler; import java.util.ArrayList; import java.util.List; public class FindPrime { public static void main(String[] args) { findPrime1(10000000); findPrime2(10000000); findPrime3(10000000); } public static void findPrime1(int n) { double start = System.currentTimeMillis(); List<Integer> primeArray = new ArrayList<Integer>(); primeArray.add(2); primeArray.add(3); int k = 0; for (int j = 5; j < n;) { for (int i = 0; i < primeArray.size(); i++) { if (primeArray.get(i) * primeArray.get(i) > j) { primeArray.add(j); break; } else if (j % primeArray.get(i) == 0) { break; } } if (k % 2 == 0) { j += 2; } else { j += 4; } k++; } System.out.println(primeArray.size()); System.out.println("程序运行时间为" + (System.currentTimeMillis() - start)); } public static List<Integer> findPrime2(int n) { double start = System.currentTimeMillis(); List<Integer> primes = new ArrayList<Integer>(); primes.add(2); for (int i = 3; i <= n; i += 2) { int tmp = (int) Math.sqrt(i) + 1; for (int j = 2; j <= tmp; j++) { if (i % j == 0) break; if (j == tmp) primes.add(i); } } System.out.println(primes.size()); System.out.println("程序运行时间为" + (System.currentTimeMillis() - start)); return primes; } public static List<Integer> findPrime3(int n) { double start = System.currentTimeMillis(); List<Integer> primes = new ArrayList<Integer>(); primes.add(2); for (int i = 3; i <= n; i += 2) { for (int j = 0; j < primes.size(); j++) { if (i % primes.get(j) == 0){ break; } if (j == primes.size() - 1) { primes.add(i); break; } } } System.out.println(primes.size()); System.out.println("程序运行时间为" + (System.currentTimeMillis() - start)); return primes; } }结果：
664579 程序运行时间为1849.0 664579 程序运行时间为9559.0 664579 程序运行时间为1620130.0数据足够大时，第一种方式最快，最后一种方式最慢
