1365: 【中级组】素数环
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:136
Solved:44
Description
有这样一个有趣的问题,输入n,然后取1<x<n中的数,围成一个环,使得相邻的两个数和为素数,并且第一个数一定是1,输出所有的可能序列有多少。比如说输入n=6,那么得到的序列是1 4 3 2 5 6、1 6 5 2 3 4这样两个序列,不难验证,这两个环是满足条件的(数字不重复)。
现在要求输入一个n,求n个数围成一圈总共有多少种素数环( 不要求输出序列 ),规定第一个数字是1。
现在要求输入一个n,求n个数围成一圈总共有多少种素数环( 不要求输出序列 ),规定第一个数字是1。
Input
输入为一行,只有一个自然数 n 。
Output
输出所有的可能的素数环序列总共有多少个。
Sample Input Copy
6
Sample Output Copy
2
HINT
提示:
- 1 <= n <= 16 。
- 数字不重复 。