Codeforces Round #749(Div. 1+Div. 2, based on Technocup 2022 Elimination Round1)-A. Windblume Ode-题解

本文主要是介绍Codeforces Round #749(Div. 1+Div. 2, based on Technocup 2022 Elimination Round1)-A. Windblume Ode-题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1) - A. Windblume Ode

传送门
Time Limit: 1 seconds
Memory Limit: 256 megabytes

Problem Description

A bow adorned with nameless flowers that bears the earnest hopes of an equally nameless person.

You have obtained the elegant bow known as the Windblume Ode. Inscribed in the weapon is an array of $n (n \geq 3)$ positive distinct integers (i.e. different, no duplicates are allowed).

Find the largest subset (i.e. having the maximum number of elements) of this array such that its sum is a composite number. A positive integer $x$ is called composite if there exists a positive integer $y$ such that $1 < y < x$ and $x$ is divisible by $y$ .

If there are multiple subsets with this largest size with the composite sum, you can output any of them. It can be proven that under the constraints of the problem such a non-empty subset always exists.

Input

Each test consists of multiple test cases. The first line contains the number of test cases $t (1 \leq t \leq 100)$ . Description of the test cases follows.

The first line of each test case contains an integer $n (3 \leq n \leq 100)$ — the length of the array.

The second line of each test case contains n distinct integers $a_1,a_2,…,a_n (1≤a_i≤200)$ — the elements of the array.

Output

Each test case should have two lines of output.

The first line should contain a single integer $x$ : the size of the largest subset with composite sum. The next line should contain $x$ space separated integers representing the indices of the subset of the initial array.

Sample Input

4
3
8 1 2
4
6 9 4 2
9
1 2 3 4 5 6 7 8 9
3
200 199 198

Sample Onput

2
2 1
4
2 1 4 3
9
6 9 1 2 3 4 5 7 8
3
1 2 3

Note

In the first test case, the subset ${a_2,a_1}$ has a sum of $9$ , which is a composite number. The only subset of size $3$ has a prime sum equal to $11$ . Note that you could also have selected the subset ${a_1,a_3}$ with sum $8 + 2 = 10$ , which is composite as it’s divisible by $2$ .

In the second test case, the sum of all elements equals to 21, which is a composite number. Here we simply take the whole array as our subset.

题目大意

给你 $n$ 个数，你可以从中删除其中几个数，使得剩下的所有的数之不是素数。
如果有多种删法，找出能够保留更多元素的一种删法，并输出保留的元素的个数及下标。

解题思路

给你的数的个数 $n$ 是 $\geq3$ 的，所以 $n$ 个数的和 $\geq6$ 。因此我们只需要看这 $n$ 个数的和是否为偶数

若和是偶数，直接就不是素数，一个都不用删，全部保留即可。
若和是奇数，其中必定包含某个数也是奇数，随便找到一个并删除即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
bool isPrime[20010] = {0, 0, 0}; // isPrime[n]代表n是否为素数
bool Prime(int n) { // 返回一个数n是否为素数for (int i = 2; i * i <= n; i++) {if (n % i == 0) {return false;}}return true;
}
void init() { // 初始化，提前计算出20000以内的所有素数for (int i = 3; i <= 20000; i++) {isPrime[i] = Prime(i);}
}
int a[111]; // 用来储存输入的数
int main() {init(); // 初始化int N;cin>>N; // N组测试用例while(N--) {int n; cd(n); // scanf("%d", &n); 这个测试用例有n个数int s = 0;for (int i = 0;i<n;i++) {cd(a[i]); // scanf("%d", &a[i]);s+=a[i]; // 求和}if (!isPrime[s]) { // 本来就不是素数，一个都不用删，直接输出即可printf("%d\n", n);for (int i = 1; i <= n; i++) {printf("%d ", i);}puts("");}else { // 本来是质数，只需要删掉一个奇数即可int del = 0; // 要删除的数的下标for (int i = 0; i < n; i++) {if (a[i] % 2) { // 如果这个数是奇数del = i + 1; // 记录下它是第几个数（存的时候是从0开始存的）break; // 找到一个就不用继续找了}}printf("%d\n", n-1); // 剩下n-1个数for (int i = 1; i <= n; i++) {if (i != del) { // 不是要被删除的那个数printf("%d ", i); // 就输出}}puts(""); // 换行}}return 0;
}