蓝桥杯2025年第十六届省赛真题-魔法科考试

小明正在参加魔法科的期末考试，考生需要根据给定的口诀组合出有效的 魔法。其中，老师给定了 n 个上半部分口诀 a₁, a₂, . . . , a_n 和 m 个下半部分口诀 b₁, b₂, . . . , b_m，均用整数表示。完整的口诀包含一个上半部分口诀和一个下半部 分口诀，当选用两个口诀 a_i 和 b_j，将组合出完整口诀 S = a_i + b_j。 

当 S 满足 S ≤ n + m 且 S 为质数时，魔法是有效的。魔法的种类只和 S 的 大小有关。如果每个上半部分口诀和每个下半部分口诀在不同的组合中可以重 复使用，小明想知道一共可能组合出多少种不同的有效魔法？

输入共三行。 

第一行为两个正整数 n, m。 

第二行为 n 个由空格分开的正整数 a₁, a₂, . . . , a_n。 

第三行为 m 个由空格分开的正整数 b₁, b₂, . . . , b_m。

输出共 1 行，一个整数表示答案。

3 4
2 3 10
3 4 5 1

3

【样例说明】 

可以组合出 3、5、7 这三个有效魔法。 

【评测用例规模与约定】 

对于 20% 的评测用例，n, m ≤ 200。 

对于 60% 的评测用例，n, m ≤ 2000。 

对于 100% 的评测用例，n, m ≤ 20000，a_i , b_i ≤ 20000。