晚上由于要帮老师算一个数学猜想，需要一个素数集合，于是写了一个。
思路：如果一个数不能被所有比它小的素数整除，那么它也是素数。
MAX就是素数的上限，计算一亿以内的素数，总共用时171330毫秒，约为171秒。
import java.util.ArrayList; public class Test{ static ArrayList<Long> list = new ArrayList<Long>();//存储素数 public static void main(String[] args){ long start = System.currentTimeMillis(); long MAX = 1_0000_0000;//一亿 findPrime(MAX); long end = System.currentTimeMillis(); System.out.println("一共有" + list.size() + "个素数，用时" + (end - start)/1000.0 + "秒"); } //找出MAX以内的所有素数并存入list private static void findPrime(long MAX){ boolean flag = true; list.add(2L); for (long n = 3; n <= MAX; n++){ //检测n是否素数。如果不能被比它小的所有素数整除，则为素数 flag = true; for(int i = 0; i < list.size(); i++){//get()方法参数必须是int if(list.get(i)*list.get(i) > n) break;//相当于常用素数算法中的sqrt(n)为上限 if(n%list.get(i) == 0){ flag = false;//能被除尽则说明非素数 break; } } if(flag) list.add(n);//保存素数 } } }网上百度了一下，找到大神的算法，只需要0.548秒
public class Prime2 { public static int calculateNumber(int Nmax) { boolean[] isPrime = new boolean[Nmax + 1]; int[] prime = new int[Nmax / 10]; int totalPrimes = 1; for (int i = 3; i <= Nmax; i += 2) isPrime[i] = true; isPrime[2] = true; prime[0] = 2; for (int i = 3; i <= Nmax; i += 2) { if (isPrime[i]) prime[totalPrimes++] = i; for (int j = 1; i * prime[j] <= Nmax && j < totalPrimes; j++){ isPrime[i * prime[j]] = false; if(i%prime[j]==0) break; } } return totalPrimes; } public static void main(String[] args) { final int Nmax = 100000000; double startTime = System.currentTimeMillis(); int primeNum = Prime2.calculateNumber(Nmax); double timeSpent = (System.currentTimeMillis() - startTime) / 1000; System.out.println("The prime numbers from 1 to " + Nmax + " is " + primeNum); System.out.println("Time spent : " + timeSpent + " s"); } }版权声明：本文为博主原创文章，未经博主允许不得转载。
转载于:https://www.cnblogs.com/kinglearnjava/p/4883332.html
相关资源：java实现计算1亿以内的素数