题解 | 魔法科考试

这题对时间要求很高，很多复杂度高的算法都不能使用

首先是判断是否为质数，传统判断方法不能用，会超时，应当使用埃氏筛

然后是判断不重复的数量，如果使用Set就会超时，应当使用布尔数组来存储存在情况

总体来说，这题还是很看重时间复杂度优化的

import java.util.Arrays;
import java.util.Scanner;
import java.util.HashSet;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		int a[]=new int[n];
		int b[]=new int[m];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
		}
		for(int i=0;i<m;i++) {
			b[i]=sc.nextInt();
		}
		HashSet<Integer> set=new HashSet();
		int max=n+m;
		boolean isPrime[]=new boolean[max+1];
		Arrays.fill(isPrime,true);
		isPrime[0]=false;
		isPrime[1]=false;
		
		for(int i=2;i*i<=max;i++) {
			if(isPrime[i]) {
				for(int j=i*i;j<=max;j+=i) {
					isPrime[j]=false;
				}
			}
		}
		
		boolean exist[]=new boolean[max+1];
		for(int i=0;i<n;i++) {
			
			for(int j=0;j<m;j++) {
				int t=a[i]+b[j];
				if(t<=n+m) {
					exist[t]=true;
				}
				
			}
		}
		int count=0;
		for(int i=0;i<=max;i++) {
			if(exist[i]&&isPrime[i]) {
				count++;
			}
		}
		System.out.println(count);

	}

}