#PQJ2648x15370. QOJ 2648_15370
QOJ 2648_15370
- 最大非质数相关子集问题 (prime.pas/c/cpp) ★问题描述: 对于给定的两个正整数 和 ,如果存在一个质数p,使得x * p = y,则称正整数 和 是 质数相关的。 对于给定的由n个正整数组成的集合S,如果S1是集合S的一个子集,且S1中任何两个正 整数都不是质数相关的,则称S1是S的一个非质数相关子集。集合S的最大非质数相关子集是 它的元素个数最多的非质数相关子集。 最大非质数相关子集问题是要求对于给定的由n个正整数组成的集合S,找出其最大非质 数相关子集。 ★编程任务: 对于给定的由n个正整数组成的集合S,计算其最大非质数相关子集的大小。 ★数据输入: 输入文件名为prime.in。 第一行一个正整数T,表示有T 组数据。 之后每组数据由2 行构成: 第一行一个正整数n,表示集合S 中的正整数个数。 第二行的n 个正整数是集合S 中的正整数。 ★结果输出: 输出文件名为prime.out。 对于每组数据输出一行,格式为“Case #T: ans”。T 为数据组号(从1 开始),ans 为答案。
★数据范围:
数据点 T N 数字大小 备注 1 10 ≤15 ≤10000
2 ≤50000000 3 ≤40 ≤10000
4 ≤100 随机生成 5
6 20 ≤5000 ≤10000 随机生成 7 ≤50000000 8 ≤5000
9 50 ≤3000 ≤10000 10 ≤50000000 ! ! ! ! 输入示例 输出示例 3 5 2 4 6 8 10 5 2 3 5 7 11 9 2 3 4 5 6 7 8 9 10 Case #1: 3 Case #2: 5 Case #3: 5