Problem Statement
When little Limak played with numbers he noticed a surprising property: If two numbers are coprime, they like each other and want to spend time together. Otherwise, they hate each other and cannot be together. Limak has a good heart and he wants numbers to be happy.
You are given an int N. Limak asks you to find a sequence of N integers t[0], t[1], ..., t[N-1] with following properties:
- Every element should be between 1 and 10^18, inclusive.
- Each pair of consecutive elements must be coprime. In other words, for every i between 0 and N-2, inclusive, the greatest common divisor of t[i] and t[i+1] must be 1.
- No other pairs of elements may be coprime. In other words, for every valid i and j such that i + 2 ⤠j the numbers t[i] and t[j] must have a common divisor greater than one.
Find any such sequence and return it as a long[]. (You may assume that for the given constraints a solution always exists.)
Definition
- Class:
- CoprimeNeighbors
- Method:
- findAny
- Parameters:
- int
- Returns:
- long[]
- Method signature:
- long[] findAny(int N)
- (be sure your method is public)
Constraints
- N will be between 2 and 500, inclusive.
Examples
2
Returns: {14, 25 }We are looking for a sequence with 2 elements: t[0] and t[1]. The values t[0] and t[1] are supposed to be coprime. The values 14 and 25 are coprime, so {14, 25} is a valid sequence.3
Returns: {1000000000000000000, 1, 1000000000000000000 }Note that the sequence is not cyclic: the first element and the last element are not adjacent. For N=3 the numbers t[0] and t[2] cannot be coprime. Also note that the returned sequence may contain duplicates.6
Returns: {14, 39, 80, 63, 26, 105 }
Back to all problems