一、找素数（填空题）
1、题目
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
素数就是不能再进行等分的整数。比如：7，117，11。而 99 不是素数，因为它可以平分为 33 等份。一般认为最小的素数是22，接着是 3，5，...3，5，...
请问，第 100002100002(十万零二)个素数是多少？
请注意：“2” 是第一素数，“3”是第二个素数，依此类推。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
2、题目解读
看题目就是让我们找到第100002个素数，题目所给的最大运行时间为1s，可以使用任意一种找素数的方法。 看了我之前那篇文章就知道，有关找寻素数的方法有五种，那我就用这道题目来让大家直观明了的比较比较其中三种方法运行速度。
3、代码
public class 找素数tkt { //欧拉筛法（埃氏筛法的优化版） public static void eulerSieve(int n){ boolean[] isPrime = new boolean[50*n]; int[] Prime=new int[n];//存放素数的数组，false为素数 isPrime[0] = isPrime[1] = true;//数字0和1都不是素数，所以赋true int count = 0; for (int i = 2; i <50*n; i++) { if (count==100002) break; if (!isPrime[i])//若当前数是素数 Prime[count++] = i;//则存入素数数组 for (int j = 0; j < count && Prime[j] * i < 50*n; j++) { isPrime[i * Prime[j]] = true; if (i % Prime[j] == 0) break;//避免重筛,使得程序更有效率 } } System.out.println(Prime[count-1]); } //埃氏筛法 static void isPrime(int n) { int[] b=new int[50*n];//通过数组b的值，为1就是素数 int[] a=new int[n];//通过数组b的值，为1就是素数 int p=0;//记录素数个数 for(int i=0;i<50*n;i++) b[i]=1; b[0]=0; b[1]=0; //准备完毕 for(int i=2;i<50*n;i++){ if (p==100002) break; if(b[i]!=0){ a[p++]=i; for(int j=2*i;j<50*n;j+=i) b[j]=0;//剔除倍数 } } System.out.println(a[p-1]); } //普通筛法 static boolean check(int n) { for(int i=2;i<=n/i;++i) { if(n%i==0) return false; } return true; } public static void main(String[] args) { long startTime1 = System.currentTimeMillis(); //获取开始时间 int ans=0; int i=2; for(;i<50*100002;++i) { if(check(i)) ans++; if(ans==100002) break; } System.out.println(i); long endTime1 = System.currentTimeMillis(); //获取结束时间 System.out.println("普通方法运行时间：" + (endTime1 - startTime1) + "ms"); //输出程序运行时间:280ms System.out.println("*********************"); long startTime2 = System.currentTimeMillis(); //获取开始时间 eulerSieve(100002);//1 299 743 long endTime2 = System.currentTimeMillis(); //获取结束时间 System.out.println("欧拉筛法运行时间：" + (endTime2 - startTime2) + "ms"); //输出程序运行时间:20ms System.out.println("*********************"); long startTime3 = System.currentTimeMillis(); //获取开始时间 isPrime(100002);//1 299 743 long endTime3 = System.currentTimeMillis(); //获取结束时间 System.out.println("埃氏筛法运行时间：" + (endTime3 - startTime3) + "ms"); //输出程序运行时间:50ms } }
可以通过三种代码的运行速度一目了然看出欧拉筛法不是快的一丁半点，所以当题目数据过大或者运行限制更小时，我们应该尽量使用欧拉筛法去降低我们代码的运行时间。
二、找素数（编程题）
1、题目
题目描述
给定一个区间 [a,b]，请你求出该区间内有多少个素数。
输入描述
输入共一行，包含两个整数 a,b。
2≤a≤b≤2147483647，b−a≤10000002
输出描述
输出一个整数，表示答案。
输入输出样例
输入
2 6
输出
3
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
2、题目解读
题目要求我们找出区间[a,b]中有多少个素数，可以看到题目所给的a，b范围很大，而且
b-1<=10000002。这样我们简单的设数组,然后去使用前面的找素数的方法，就不行了，会超时，我们就需要在原来的方法上面进行改进。
如下面，就算是使用最快的欧拉筛法最后一个用例也会超时。所有在实际问题中也要学会创新，寻找到对应的解决方法。
import java.util.*; public class Main { public static final int MAX=1000005; public static boolean isprime[]=new boolean[MAX]; public static boolean primelist[]=new boolean[MAX]; public static int seg_sieve(int a,int b) { boolean[] isPrime = new boolean[b + 1]; int[] Prime = new int[b];//存放素数的数组，false为素数 isPrime[0] = isPrime[1] = true;//数字0和1都不是素数，所以赋true int count = 0; int x=0; for (int i = 2; i < b + 1; i++) { if (!isPrime[i]) { Prime[count++] = i;//则存入素数数组 if (i>=a) x++; } for (int j = 0; j < count && Prime[j] * i < b + 1; j++) { isPrime[i * Prime[j]] = true; if (i % Prime[j] == 0) break;//避免重筛,使得程序更有效率 } } return x; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); int k = seg_sieve(a,b); System.out.println(k); } }
3、代码
在开头说的文章中，不必一直循环到n-1，因为如果a*b=n，则其中必有一个大于sqrt(n) ，一个小于sqrt(n),，所以我们把循环范围缩小到√n。所以我们可以创建两个数组，用来分别标记[2,√n]中的素数，另一个数组用来标记[a，b]中的素数。找到在[2,√n]中的素数，然后去[a,b]数组中找这个素数的倍数，判定其不是素数，把[2，√n]中的素数遍历完，[a,b]数组中的素数也都找出来了。
import java.util.Scanner; public class Main{ static int N = 1000005; static boolean vis[] = new boolean[N];//标记[2，√b]中的素数 static boolean PrimeN[] = new boolean[N];//标记[a,b]中的素数 public static void main(String[] args) { Scanner scan = new Scanner(System.in); int a = scan.nextInt(); int b = scan.nextInt(); PrimeN_sieve(a, b); } static void PrimeN_sieve(int x, int y) { for (int i = 2; i <= Math.sqrt(y); i++) { if (!vis[i]) { //标记[2，√b]中的素数 for (int j = i * i; j < Math.sqrt(y); j += i) { vis[j] = true; } //标记[a,b]中的素数 //Math.max(2, (a - 1 + i) / i) * i是找到大于a的第一个i的倍数,然后+i，把所有[a,b] //中i的倍数都遍历一遍 for (int k = Math.max(2, (x + i - 1) / i) * i; k < y + 1; k += i) { PrimeN[k - x] = true; } } } //计算出[a,b]中素数的个数 int num = 0; for (int q = 0; q <= y - x; q++) { if (!PrimeN[q]) { num++; } } System.out.println(num); } }
