Problem:
 Score : 600 points    Problem Statement Nagase is a top student in high school. One day, she's analyzing some properties of special sets of positive integers.  She thinks that a set S = \{a_{1}, a_{2}, ..., a_{N}\} of distinct positive integers is called special if for all 1 \leq i \leq N , the gcd (greatest common divisor) of a_{i} and the sum of the remaining elements of S is not  1 .  Nagase wants to find a special set of size N . However, this task is too easy, so she decided to ramp up the difficulty. Nagase challenges you to find a special set of size N such that the gcd of all elements are 1 and the elements of the set does not exceed 30000 .      Constraints  3 \leq N \leq 20000         Input Input is given from Standard Input in the following format:  N       Output Output N space-separated integers, denoting the elements of the set S . S must satisfy the following conditions :   The elements must be distinct positive integers not exceeding 30000 .  The gcd of all elements of S is 1 , i.e. there does not exist an integer d > 1 that divides all elements of S .  S is a special set.   If there are multiple solutions, you may output any of them. The elements of S may be printed in any order. It is guaranteed that at least one solution exist under the given contraints.        Sample Input 1 3      Sample Output 1 2 5 63  \{2, 5, 63\} is special because gcd(2, 5 + 63) = 2, gcd(5, 2 + 63) = 5, gcd(63, 2 + 5) = 7 . Also, gcd(2, 5, 63) = 1 . Thus, this set satisfies all the criteria.  Note that \{2, 4, 6\} is not a valid solution because gcd(2, 4, 6) = 2 > 1 .       Sample Input 2 4      Sample Output 2 2 5 20 63  \{2, 5, 20, 63\} is special because gcd(2, 5 + 20 + 63) = 2, gcd(5, 2 + 20 + 63) = 5, gcd(20, 2 + 5 + 63) = 10, gcd(63, 2 + 5 + 20) = 9 . Also, gcd(2, 5, 20, 63) = 1 . Thus, this set satisfies all the criteria.

Solution (Python):
N = int(input())
def gener():
    i = 2
    while True:
        if i%2==0 or i%3==0 or i%5==0:
            yield i
        i+=1
gen = gener()
ans = []
for j in range(N-2):
    ans.append(gen.__next__())
S = sum(ans)
while True:
    g = gen.__next__()
    p = S + g
    if p%2==0 or p%3==0 or p%5==0:
        ans.append(g)
        break
while True:
    g = gen.__next__()
    p2 = p + g
    if p2%30==0:
        ans.append(g)
        break
print(*ans)

Solution (Python):
import fractions

def check(S):
  g = S[0]
  for s in S:
    g = fractions.gcd(g, s)
  if g>1:
    return False
  for s in S:
    if fractions.gcd(s, sum(S)-s)==1:
      return False
  return True

import sys
sys.setrecursionlimit(100000)

N = input()
P = [2,3,5,7]
def BT(S, s):
  for a in xrange(S[-1]+1, 30001):
    ok = False
    for p in P:
      if a%p==0:
        ok = True
        break
    if ok:
      S.append(a)
      s += a
      if len(S)==N:
        if s%210==0:
          print " ".join(map(str, S))
          
          exit(0)
      else:
        BT(S, s)
      S.pop()
      s -= a
BT([2], 2)

Solution (Python):
n = input()

ans = [2,5,20,63]

if n == 3:
    print 2,5,63
    exit(0)

p = 90
while (n - len(ans))%44 != 0:
    ans.append(p)
    p += 30

while len(ans) < n:
    if p % 2 == 0 or p % 5 == 0 or p % 3 == 0:
        ans.append(p)
    p += 1

def gcd(a,b):
    if a == 0:return b
    return gcd(b % a, a)

s = sum(ans)
    
for x in ans:
    print x,
print ""