第一个素数是2,求第50000个素数
问题描述:
已知第一个素数是2,第二个素数是3,求第50000个素数。
求素数这个问题本身并不难,这个问题主要是对程序运行时间上的要求。要求第50000个素数,
以常规的逐个查找很难得出结果,递归也容易出现栈溢出的情况。因此需要提出更简洁高效的方法。
解题思路:
首先在做一个静态的List(lst)用来装求过的素数,初始化时将第一个素数装入lst中。因此从第二个素数开始求,
由于所有的非素数必定可被某个小于它的素数整除,因此在求n个素数时,只要某个大于第n-1个素数的数,不被第1个到第
n-1个素数中的数整除即为第n个素数。例如:前四个素数为{2,3,5,7},要求第5个,从8开始,由于8%2=0,9%3=0,10%2=0,
11既满足要求。此时lst为{2,3,5,7,8} lst的长度为5,因此lst的最后一个11即为所求数。
//2017.03.16 public class W03162 { static List<Integer> lst = new ArrayList<Integer>(); //装着所有以求得的素数 static{ lst.add(2); //初始化时装入第一个素数2 } static boolean is_su_shu(int x){ //判断一个数是否是素数 for(int i : lst){ if(x%i==0) return false; } return true; } static int su_shu(int x){ for(int i=lst.get(lst.size()-1)+1;;i++){ //从lst中最后一个数开始,求下一个素数 if(is_su_shu(i)==false) continue; if(lst.size()==x) return lst.get(lst.size()-1);//当lst中装的素数装满x个时 lst.add(i); //lst中最后一个即为所求数 }
} public static void main(String[] args){ long a = System.currentTimeMillis(); System.out.println(su_shu(50000)); //打印出第50000个素数 long b = System.currentTimeMillis(); System.out.println(b-a); //打印出运行时间 } }
运行结果图:
如图所示,第50000个素数是611953
而程序所用时间为22589毫秒,还是很慢的,需要进一步优化。