100963: [AtCoder]ABC096 D - Five, Five Everywhere
Description
Score: $400$ points
Problem Statement
Print a sequence $a_1, a_2, ..., a_N$ whose length is $N$ that satisfies the following conditions:
- $a_i$ $(1 \leq i \leq N)$ is a prime number at most $55$ $555$.
- The values of $a_1, a_2, ..., a_N$ are all different.
- In every choice of five different integers from $a_1, a_2, ..., a_N$, the sum of those integers is a composite number.
If there are multiple such sequences, printing any of them is accepted.
Notes
An integer $N$ not less than $2$ is called a prime number if it cannot be divided evenly by any integers except $1$ and $N$, and called a composite number otherwise.
Constraints
- $N$ is an integer between $5$ and $55$ (inclusive).
Input
Input is given from Standard Input in the following format:
$N$
Output
Print $N$ numbers $a_1, a_2, a_3, ..., a_N$ in a line, with spaces in between.
Sample Input 1
5
Sample Output 1
3 5 7 11 31
Let us see if this output actually satisfies the conditions.
First, $3$, $5$, $7$, $11$ and $31$ are all different, and all of them are prime numbers.
The only way to choose five among them is to choose all of them, whose sum is $a_1+a_2+a_3+a_4+a_5=57$, which is a composite number.
There are also other possible outputs, such as 2 3 5 7 13
, 11 13 17 19 31
and 7 11 5 31 3
.
Sample Input 2
6
Sample Output 2
2 3 5 7 11 13
- $2$, $3$, $5$, $7$, $11$, $13$ are all different prime numbers.
- $2+3+5+7+11=28$ is a composite number.
- $2+3+5+7+13=30$ is a composite number.
- $2+3+5+11+13=34$ is a composite number.
- $2+3+7+11+13=36$ is a composite number.
- $2+5+7+11+13=38$ is a composite number.
- $3+5+7+11+13=39$ is a composite number.
Thus, the sequence 2 3 5 7 11 13
satisfies the conditions.
Sample Input 3
8
Sample Output 3
2 5 7 13 19 37 67 79