Problem:
 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

Solution (Python):
def main():
    offset = 55555
    primes = [True for i in range(offset + 1)]
    primes[2] = True
    c=2
    while c <= offset:
        if primes[c] == True:
            count = 2 * c
            while count <= offset:
                primes[count] = False
                count += c
            c += 1
        else:
            c += 1
    pc = 0
    array_of_primes=[]
    for i in range(2, offset + 1):
        if primes[i]:
            pc += 1
            array_of_primes.append(i)

    n = int(input())
    arr = []
    count = 0
    for i in array_of_primes:
        if count == n:
            break
        if i % 5 == 1:
            arr.append(i)
            count += 1
    for i in arr:
        print(i, end= " ")
                

main()

Solution (Python):
n = int(input())

def prime():
    p = [2]
    m = 3
    while m < 1400:
        for i in p:
            if m % i == 0:
                break
        else:
            p.append(m)
        m += 2
    return p

ans = []
p = prime()
q = p[1:]

while len(ans) < n:
    for i, q_ in enumerate(q):
        if q_ % 5 == 1:
            ans.append(q_)
            del q[i]
            break

print(' '.join([str(s) for s in ans]))

Solution (Python):
lst=[2,11,31,41,61,71,101,151,181,191,211,241,251
,271,281,311,331,401,421,491,521,541
,571,601,631,641,661,691,701,751,761,1021
,1031,1051,1061,1091,1201,2221,3001,3011
,3821,4421,4441,4451,4111,4391,8861,8221,9901
,8831,6011,6581,7001,8171,6151,6701]
n=int(input())
x=''
for i in range(n):
    x+=str(lst[i])+' '
print(x)

Solution (Python):
n = int(input())

isprime = [True for i in range(55556)]
isprime[0] = False
isprime[1] = False
for i in range(4, 55556, 2):
    isprime[i] = False
for i in range(3, 237):
    if isprime[i]:
        for j in range(i*3, 55556, i*2):
            isprime[j] = False
ans = []
for i in range(55556):
    flag = False
    if isprime[i] and i % 5 == 1:
        ans.append(i)
    if len(ans) == n:
        break
for i in ans:
    print(i, end=' ')

Solution (Python):
import sys
N = int(input())

n = 10000
primeN = []
tmp = 2
for i in range(2, n):
    if primeN:
        for j in range(len(primeN)):
            if i % primeN[j] == 0:
                break
            else:
                if j == len(primeN) - 1:
                    primeN.append(i)
    else:
        if n > tmp:
            primeN.append(i)

ans = []
for i in primeN:
    if len(ans)==N:
        for j in ans:
            print(j)
        sys.exit()

    if i%5==1:
        ans.append(i)

Solution (Python):
import math
import random
m = int(input())
n = 10000
def sosuuhantei(x):
    p = x
    if p < 2:
        return false
    elif  n == 2:
        return p
    else:
        for i in range(3,math.floor(math.sqrt(x)) + 1,2):
            if x % i == 0:
                return False
        else:
             return x
sosulist = []
 
if n < 2:
    None
elif n == 2:
    sosulist.append(2)
else:
    sosulist.append(2)
    for i in range(3,n+1,2):
        sosulist.append(sosuuhantei(i))
        
while False in sosulist:
    sosulist.remove(False)

s = []
for i in range(len(sosulist)):
    if sosulist[i] % 5 == 1:
        s.append(sosulist[i])

strs = ''
for i in range(m):
    strs = strs + str(s[i]) + ' '
print(strs)

Solution (Python):
N=int(input())
import math
def primes(a,x):
    if x < 2: return []
    primes=[i for i in range(x)]
    primes[1]=0
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0
    return [prime for prime in primes if prime>a and prime%5==1]
L=primes(0,55555)[0:N]
print(' '.join(map(str, L)))

Solution (Python):
n = int(input())

max_prime = 555555

primes = [True for i in range(max_prime+1)]

for i in range(2, max_prime):
    if primes[i]:
        for j in range(i+i, max_prime+1, i):
            primes[j] = False

primes[0] = False
primes[1] = False

primes_num = [i for i, el in enumerate(primes) if el][2:]

ans = []

for p in primes_num:
    if str(p)[len(str(p))-1] == str(1) and p % 6 == 1:
        ans.append(p)

    if len(ans) == n:
        break


for p in ans:
    print(p, end=" ")

print()

Solution (Python):
n = int(input())
def sieve(limit):
    a = [True] * limit
    a[0] = a[1] = False
    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):
                a[n] = False
a = list(sieve(55555))
ans = []

for i in a:
    if i % 5 == 1:
        ans.append(i)
    if len(ans) == n:
        break
print(*ans)

Solution (Python):
import math
def primes(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0 
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0
    return [prime for prime in primes if prime != 0]

p = primes(55556)
p = [i for i in p if i%5 == 4]
p = p[:int(input())]
print(" ".join(map(str,p)))

Solution (Python):
N = int(input())
erat = [True for i in range(55556)]
erat[0], erat[1] = False, False
i = 2
while i*i<55556:
    if erat[i]:
        j = 2
        while i*j<55556:
            erat[i*j] = False
            j += 1
    i += 1
    

ans = []
for i in range(len(erat)):
    if len(ans)==N:
        break
    if erat[i]:
        if i%5==1:
            ans.append(i)

print(*ans)

Solution (Python):
table = [True for i in range(1, 100000)]

def generate():
	global table
	for i in range(2, len(table)):
		if table[i] == True:
			for j in range(i * i, len(table), i):
				table[j] = False

	table[1] = False
	
def prime(x):
	if table[1] == True:
		generate()

	return table[x]

v = []
for i in range(11, 55556, 10):
	if prime(i):
		v.append(i)

n = int(raw_input())

for i in range(n):
	print v[i],

Solution (Python):
print(' '.join(map(str, [11, 31, 41, 61, 71, 101, 131, 151, 181, 191, 211, 241, 251, 271, 281, 311, 331, 401, 421, 431, 461, 491, 521, 541, 571, 601, 631, 641, 661, 691, 701, 751, 761, 811, 821, 881, 911, 941, 971, 991, 1021, 1031, 1051, 1061, 1091, 1151, 1171, 1181, 1201, 1231, 1291, 1301, 1321, 1361, 1381][:int(input())])))

Solution (Python):
n = int(input())
import math
import random
s = [1 for i in range(55555+1)]
s[0], s[1] = 0, 0
for i in range(2, int(math.sqrt(55555))+1):
    if s[i] != 0:
        for j in range(i*2, 55555, i):
            s[j] = 0
prime = []
for i in range(55555+1):
    if s[i] == 1:
        if str(i)[-1] == '1':
            prime.append(i)

def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1




ans = ''
for i in range(n):
    ans += str(prime[i]) + ' '
print(ans[:-1])

quit()

Solution (Python):
n = int(input())

work = [True] *  55556
work[0] = False
work[1] = False
primes = []
for i in range(55556):
    if work[i]:
        for j in range(2* i, 55556, i):
            work[j] = False

ret = [2]
i = 6
while len(ret) != n:
    i += 5
    if work[i]:
        ret.append(i)

print(' '.join(map(str,ret)))

Solution (Python):


import numpy as np
n = int(input())

def sosu(x):
    for i in range(2,int(np.sqrt(x))+1):
        if x%i == 0: return False
    return True

c = 2
ans = []
while 1:
    y = 20*c + 1
    if sosu(y):
        ans.append(y)
    c += 1
    if len(ans) == n: break

l = ""
for i in range(len(ans)):
    l += str(ans[i])
    l += " "

print(l[:len(l)-1])

Solution (Python):
from itertools import combinations

p = [1]*555555
p[0] = p[1] = 0
for i in xrange(2, int(555555**0.5) + 1):
    if p[i]:
        p[2*i::i] = [0]*len(p[2*i::i])

ans = []
for i in xrange(55555):
    if p[i] and str(i)[-1] == "1":
        ans.append(i)

N = int(raw_input())
print " ".join(map(str, ans[:N]))

Solution (Python):
N = int(input())
prime = []
for i in range(1, 150):
    n = 1 + 10 * i
    for j in range(2, n+1):
        if n % j == 0:
            if n == j:
                prime.append(str(n))
            else:
                break

print(' '.join(prime[0:N]))

Solution (Python):
n = int(input())
list1 = [3, 13, 23, 43, 53, 73, 83, 103, 113, 163, 173, 193, 223, 233, 263, 283, 293, 313, 353, 373, 383, 433, 443, 463, 503, 523, 563, 593, 613, 643, 653, 673, 683, 733, 743, 773, 823, 853, 863, 883, 953, 983, 1013, 1033, 1063, 1093, 1103, 1123, 1153, 1163, 1193, 1213, 1223, 1283, 1303]
del list1[n:55]
ma = list(map(str,list1))
print(' '.join(ma))

Solution (Python):
import math

N = int(raw_input())

def genprimes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0

    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes = genprimes(55556)

ans = []
for p in primes:
    if str(p)[-1] == '1':
        ans.append(p)

print(' '.join(map(str, ans[:N])))

Solution (Python):
import math

N = int(input())
num = 55555
input_list = [False if i%2 == 0 or i%3 == 0 or i%5==0 else True for i in range(num)]
input_list[0] = input_list[1] = False
input_list[2] = input_list[3] = input_list[5] = True
sqrt = math.sqrt(num)

for serial in range(3, num, 2):
    if serial >= sqrt:
        break
    for s in range(serial ** 2, num, serial):
        input_list[s] = False

ans = []
count = 0
for i in range(11111):
    if input_list[5*i-1]:
        ans.append(5*i-1)
    if len(ans) == N:
        break

ans2 = ""
for i in range(len(ans)):
    ans2 += str(ans[i])
    if i != len(ans)-1:
        ans2 += " "

print(ans2)

Solution (Python):
def P(p):
    if p%2==0:
        return False
    for i in range(3,int(p**0.5//1+1),2):
        if p%i==0:
            return False
    return True

def main():
    N = int(input())
    p = [2,3,5]
    for i in range(7, 55555):
        if P(i):
            p.append(i)

    ans = [3,]
    for i in range(5, len(p)):
        if str(p[i])[-1] in "3":
            ans.append(p[i])
        if len(ans)==N:
            return " ".join(map(str, ans))
    return p

if __name__ == '__main__':
    print(main())

Solution (Python):
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

n = int(input())

c = []
k=0
for i in range(n):
    
    while(not is_prime(5 * k + 2)):
        k = k + 1
    
    c.append(5 *k + 2)
    k=k+1

print(' '.join(map(str, c)))

Solution (Python):
sosuulist =[]

for i in range(2,2000):
    count =0
    for j in range(2,i):
        if int(i)%int(j)==0:
            count =10000
            j =i
        else:
            j +=1
    if count==0:
        sosuulist.append(i)
        i +=1
    else:
        i +=1


sosuulist2=[]
for l in range(len(sosuulist)):
    if int(sosuulist[l])%10==7:
        sosuulist2.append(sosuulist[l])
        l +=1
    else:
        l +=1
        

answer =""
num = input()
for k in range(int(num)):
    answer=answer+str(sosuulist2[k])+" "
answer=answer.rstrip()
print(answer)

Solution (Python):
import sys
import math
sys.setrecursionlimit(10000)

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 

    
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

def is_prime(x):
    if x < 2: return False 
    if x == 2 or x == 3 or x == 5: return True 
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False 

    
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

n = int(input())


p = primes(55555)

q = []
for i in p:
    if(i % 5 == 1): q.append(i)
    if(len(q) == n): break

for i in range(len(q)):
    if(i == len(q)-1): print(q[i])
    else: print(q[i], end=" ")

Solution (Python):
import math

n=int(input())


primes = list(range(2, 2000))
root_n = int(2000 ** (1/2)) + 1

i = j = 0
for p, q in enumerate(primes):
    if q >= root_n:
        break
    elif q:
        for r in range(p + q, 2000 - 2, q):
            if primes[r]:
                primes[r] = 0
result = [str(2)]
Plist = [primes[x] for x in range(len(primes)) if primes[x] > 0 and primes[x]%5 == 1]
for i in range(n-1):
    result.append(str(Plist[i]))
print(' '.join(result))

Solution (Python):
N = int(input())
limitN = 60000
P = [0]*limitN
listP = []
for i in range(2,limitN):
    if P[i] == 0:
        listP.append(i)
        j=1
        while i*j < limitN:
            P[i*j] = 1
            j+=1
Ans = list(map(str,filter(lambda x: x%5==1,listP)))
print(" ".join(Ans[0:N]))

Solution (Python):
def main():
    N = int(input())

    lst = erastosthenes(55555)
    prime_lst = [2] + [i for i in range(3, 55556, 2) if lst[i]]

    ans = []
    for i in prime_lst:
        mod = i % 10
        if mod == 1:
            ans.append(i)
    print(*ans[:N], sep=' ')


def erastosthenes(n):
    prime = [0, 1] * ((n + 1) // 2)
    if not n % 2:
        prime += [0]
    prime[1], prime[2] = 0, 1

    sqrt = n ** 0.5
    i = 3
    while i <= sqrt:
        for j in range(i ** 2, n + 1, i):
            prime[j] = 0
        i += 2
    return prime

main()

Solution (Python):
L=[2,11,31,41,61,71,101,131,151,181,191,211,241,251,271,281,311,331,
  401,421,431,461,491,521,541,571,601,631,641,661,701,751,761,811,821,
  881,911,941,971,991,1021,1031,1051,1061,1091,1151,1171,1181,
  1201,1231,1291, 1301,1321,1361,1381,1451,1471]
N = int(input())
A = []
for i in range(N):
    A.append(L[i])
print(' '.join(map(str, A)))

Solution (Python):
import math
def primes(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0
    return [prime for prime in primes if prime != 0]

n = int(input())
p=primes(10000)
pc = []
for v in p:
    if (v-1)%5==0:
        pc.append(v)
        if len(pc)==n:
            break
print(' '.join(map(str, pc)))

Solution (Python):
def sieve(n):
    primes = []
    candidates = list(range(2, n + 1))
    v = candidates[0]
    while v ** 2 <= n:
        primes.append(v)
        candidates.pop(0)
        candidates = list(filter(lambda x: x % v != 0, candidates))
        v = candidates[0]
    primes += candidates
    return primes

N = int(input())
L = sieve(55556)

n = 0
ans = []
for l in L:
    if (l + 1) % 5 == 0:
        ans.append(str(l))
        n += 1
    if n == N:
        break

print(' '.join(ans))

Solution (Python):
s = [11, 31, 41, 61, 71, 101, 131, 151, 181, 191, 211, 241, 251, 271, 281, 311, 331, 401, 421, 431, 461, 491, 521, 541, 571, 601, 631, 641, 661, 691, 701, 751, 761, 811, 821, 881, 911, 941, 971, 991, 1021, 1031, 1051, 1061, 1091, 1151, 1171, 1181, 1201, 1231, 1291, 1301, 1321, 1361, 1381, 1451, 1471, 1481, 1511, 1531, 1571, 1601, 1621, 1721, 1741, 1801, 1811, 1831, 1861, 1871, 1901, 1931, 1951, 2011, 2081, 2111, 2131, 2141, 2161, 2221, 2251, 2281, 2311, 2341, 2351, 2371, 2381, 2411, 2441, 2521, 2531, 2551, 2591, 2621, 2671, 2711, 2731, 2741, 2791, 2801, 2851, 2861, 2971, 3001, 3011, 3041, 3061, 3121, 3181, 3191, 3221, 3251, 3271, 3301, 3331, 3361, 3371, 3391, 3461, 3491, 3511, 3541, 3571, 3581, 3631, 3671, 3691, 3701, 3761, 3821, 3851, 3881, 3911, 3931]

n = int(input())
o = ""
for i in range(n):
    o+=str(s[i])+" "
print(o)

Solution (Python):
prime = [2]
for i in range(10000):
    if i == 0 or i == 1 or i == 2:
        continue
    a = True
    for p in prime:
        if i % p == 0:
            a = False
            break
    if a == True:
        prime.append(i)
n = input()
a = []
for p in prime:
    if p % 5 == 1:
        a.append(p)
        if len(a) == n:
            break
b = ''
for c in a:
    b += str(c) + ' '
b = b[:-1]
print b

Solution (Python):

import math
n = int(input())
prime = [2]
res = [2]
for i in range(3, 55555):
    isp = True
    for j in prime:
        if int(math.sqrt(i)) < j:
            break
        if i % j == 0:
            isp = False
            break
    if isp:
        prime.append(i)
        if i % 5 == 2:
            res.append(i)
            if len(res) == n:
                break
for i in range(0, n):
    print(res[i], end="")
    if i == n - 1:
        break
    print(" ", end="")

Solution (Python):
import math
MAX = 55555

n = int(input())
lst = [1 for i in range(MAX)]
lst[0] = lst[1] = 0
for i in range(int(math.sqrt(MAX)) + 1):
  if lst[i]:
    for j in range(i * i, MAX, i):
      lst[j] = 0
primes = [i for i in range(MAX) if lst[i]]
ans = [11,31,41,61,71]
count = n - 5
if count > 0:
  for i in range(101,MAX + 1,5):
    if i in primes:
      ans.append(i)
      count -= 1
      if count == 0:
        break
print(" ".join(list(map(str,ans))))

Solution (Python):
import math
N = 55555
n = int(input())
p = []
for i in [0]*(N+1):
  p.append(1)

p[0] = 0
p[1] = 0

i = 2
while i <= N/2:
  if p[i] == 1:
    j = 2*i
    while j <= N:
      p[j] = 0
      j += i
  i += 1

ans = [2]
j = 2
for i in range(n-1):
  while 5*j + 1 < N and p[5*j+1] == 0:
    j += 1
  ans.append(5*j+1)
  j += 1
print(' '.join(map(str, ans)))

Solution (Python):
p = [11,31,41,61,71,101,131,151,181,191,211,241,251,271,281,311,331,401,421,431,461,491,521,541,571,601,631,641,661,691,701,751,761,811,821,881,911,941,971,991,1021,1031,1051,1061,1091,1151,1171,1181,1201,1231,1291,1301,1321,1361,1381,1451,1471,1481,1511,1531,1571,1601,1621,1721,1741,1801,1811,1831,1861,1871,1901,1931,1951,2011,2081,2111,2131,2141,2161,2221,2251,2281,2311,2341,2351,2371,2381,2411,2441,2521,2531,2551,2591,2621,2671,2711,2731,2741,2791,2801,2851,2861,2971,3001,3011,3041,3061,3121,3181,3191,3221,3251,3271,3301,3331,3361,3371,3391,3461,3491,3511,3541,3571,3581,3631,3671,3691,3701,3761,3821,3851,3881,3911,3931,4001,4021,4051,4091,4111,4201,4211,4231,4241,4261,4271,4391,4421,4441,4451,4481,4561,4591,4621,4651,4691,4721,4751,4801,4831,4861,4871,4931,4951,5011,5021,5051,5081,5101,5171,5231,5261,5281,5351,5381,5431,5441,5471,5501,5521,5531,5581,5591,5641,5651,5701,5711,5741,5791,5801,5821,5851,5861,5881,5981,6011,6091,6101,6121,6131,6151,6211,6221,6271,6301,6311,6361,6421,6451,6481,6491,6521,6551,6571,6581,6661,6691,6701,6761,6781,6791,6841,6871,6911,6961,6971,6991,7001,7121,7151,7211,7321,7331,7351,7411,7451,7481,7541,7561,7591,7621,7681,7691,7741,7841,7901,7951,8011,8081,8101,8111,8161,8171,8191,8221,8231,8291,8311,8431,8461,8501,8521,8581,8641,8681,8731,8741,8761,8821,8831,8861,8941,8951,8971,9001,9011,9041,9091,9151,9161,9181,9221,9241,9281,9311,9341,9371,9391,9421,9431,9461,9491,9511,9521,9551,9601,9631,9661,9721,9781,9791,9811,9851,9871,9901,9931,9941,10061,10091,10111,10141,10151,10181,10211,10271,10301,10321,10331,10391,10501,10531,10601,10631,10651,10691,10711,10771,10781,10831,10861,10891,11071,11131,11161,11171,11251,11261,11311,11321,11351,11411,11471,11491,11551,11621,11681,11701,11731,11801,11821,11831,11941,11971,11981,12011,12041,12071,12101,12161,12211,12241,12251,12281,12301,12391,12401,12421,12451,12491,12511,12541,12601,12611,12641,12671,12721,12781,12791,12821,12841,12911,12941,13001,13121,13151,13171,13241,13291,13331,13381,13411,13421,13441,13451,13591,13681,13691,13711,13721,13751,13781,13831,13841,13901,13921,13931,14011,14051,14071,14081,14221,14251,14281,14321,14341,14401,14411,14431,14461,14551,14561,14591]
print(' '.join(map(str,p[:int(input())])))

Solution (Python):
def candidates(n):
    m = [True for _ in range(n + 1)]
    m[0] = False
    m[1] = False

    for i in range(2, n + 1):
        if not m[i]:
            continue
        
        for j in range(i * 2, n + 1, i):
            m[j] = False

    c = []

    for i, x in enumerate(m):
        if x and i % 5 == 1:
            c.append(i)
    
    return c

def main():
    c = candidates(55555)
    n = int(input())
    print(*c[:n])

main()