By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
译文:
观察第一组质数可知,第6位质数为13,那么第10001位质数是多少呢?
============================
第一次code:
import java.util.ArrayList; import java.util.List; public class Main { public static void main (String[] args) { System.out.println(binarySearch(prime(200000),10000)); } /** * 对n个数进行求质数 * 所求出质数存到ArrayList数组中 * @param n * @return */ public static List prime(int n) { List<Integer>list = new ArrayList<Integer>(); for(int i=2;i<n;i++) { String b="YES"; int [] a = new int[n]; for(int j=2;j<i;j++) { a[j]=i % j; if(a[j] == 0) { b="NO";break; } } if(b.equals("YES")) { list.add(i); } } return list; } /** * 对ArrayList数组进行折半二查法查找 * @param x * @param n * @return */ public static int binarySearch(List x, int n) { int start = 0; int end = x.size() - 1; int mid = -1; while (start <= end) { mid = (start + end) / 2; if (mid == n) { return (int) x.get(mid); } else if (mid > n) { end = mid - 1; } else if (mid < n) { start = mid + 1; } } return -1; } }
结果为:104743
时间效率:求出200000内的所有质数后,再检索出第10001位质数,所花时间为43638毫秒。