ZT7 小红的排列构造

描述

小红希望你构造一个排列，满足对于排列中的每一项ai​都满足：ai​+i均不是质数（下标i从1开始）。你能帮帮她吗？

长度为n的排列是指：一个长度为n的数组，其中1到n每个正整数恰好出现1次。例如[2,1,3]是排列，而[1,3,4,3]不是排列。    

输入描述：

一个正整数n，代表待构造的排列长度。
1≤n≤10^5

输出描述：

如果无法构造，则输出-1。
否则输出一个长度为n的满足要求的排列。有多解时输出任意即可。

示例1

输入：

1

输出：

-1

说明：

长度为1的排列只有[1]，由于1+1=2是质数，不合法。所以不存在可以构造的排列。

示例2

输入：

10

输出：

9 4 6 2 1 8 3 10 7 5

说明：

a1​+1=9+1=10，不是质数。
a2​+2=4+2=6，不是质数。
a3​+3=6+3=9，不是质数。
以此类推，每个元素ai​加上i均不是质数。符合要求。

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.构造一个排列

2.对于排列中的每一项ai都满足

3.ai+i（当前的下标，从1开始）不是质数

4.如果可以则输出长度为n的排列

5.如果不可以输出-1

二、解题思路

1.如果n为1，则无法构造

1 + 1 = 2是质数

2.如果n为2

排列的方法有两种一种是

1 2

一种是

2 1

由于1不能在第一个位置（+1=2是质数）

所以看看第二种排列

2 + 1 = 3是质数（所以也不可以）

所以输出-1

3.再看看如果n为3

1 2 3不行

2 1 3不行（前面不能放1和2）

3 1 2不行（1+2=3是质数）

3 2 1（可以，3+1=4，2+2=4，1+3=4）

4.再来看看n如果是4的话呢

（1，2肯定不能放前面）

3 2 1 4（4+4=8，不是质数）

5.现在找到规律了，前面不能放1，2

后面的话，只需要放和自己相同的数字就行了

因为自己和自己相加一定是2的倍数，就不是质数了

三、具体步骤

使用的语言是C

#include <stdio.h>

int main() {
    int n;
    while (scanf("%d", &n) != EOF) { 
        if(n < 3) {
            printf("-1\n");
            return 0;
        } else {
            printf("3 2 1");
            for(int i = 4; i <= n; i++) {
                printf(" %d", i);
            }
        }
    }
    return 0;
}