Problem:
Problem B: Monday-Saturday Prime Factors Chief Judge's log, stardate 48642.5.
We have decided to make a problem from elementary number theory.
The problem looks like finding all prime factors of a positive integer,
but it is not. A positive integer whose remainder divided by 7 is either 1 or 6 is called
a 7 N +{1,6} number.
But as it is hard to pronounce,
we shall call it a Monday-Saturday number . For Monday-Saturday numbers a and b ,
we say a is a Monday-Saturday divisor of b if there exists a Monday-Saturday number x such that a x = b .
It is easy to show that
for any Monday-Saturday numbers a and b ,
it holds that a is
a Monday-Saturday divisor of b if and only if a is a divisor of b in the usual sense. We call a Monday-Saturday number a Monday-Saturday prime if it is greater than 1 and has no Monday-Saturday divisors
other than itself and 1.
A Monday-Saturday number which is a prime in the usual sense
is a Monday-Saturday prime
but the converse does not always hold.
For example, 27 is a Monday-Saturday prime
although it is not a prime in the usual sense.
We call a Monday-Saturday prime
which is a Monday-Saturday divisor of a Monday-Saturday number a a Monday-Saturday prime factor of a .
For example, 27 is one of the Monday-Saturday prime factors of 216,
since 27 is a Monday-Saturday prime
and 216 = 27 × 8 holds.  Any Monday-Saturday number greater than 1
can be expressed as a product of one or more Monday-Saturday primes.
The expression is not always unique
even if differences in order are ignored.
For example, 216 = 6 × 6 × 6 = 8 × 27 holds.  Our contestants should write a program that outputs
all Monday-Saturday prime factors
of each input Monday-Saturday number. Input The input is a sequence of lines each of which contains a single
Monday-Saturday number.
Each Monday-Saturday number is greater than 1
and less than 300000 (three hundred thousand).
The end of the input is indicated by a line
containing a single digit 1. Output For each input Monday-Saturday number,
it should be printed, followed by a colon `:'
and the list of its Monday-Saturday prime factors on a single line.
Monday-Saturday prime factors should be listed in ascending order
and each should be preceded by a space.
All the Monday-Saturday prime factors should be printed only once
even if they divide the input Monday-Saturday number more than once. Sample Input 205920
262144
262200
279936
299998
1 Output for the Sample Input 205920: 6 8 13 15 20 22 55 99
262144: 8
262200: 6 8 15 20 50 57 69 76 92 190 230 475 575 874 2185
279936: 6 8 27
299998: 299998

Solution (Python):
this_prime_num = [0 for i in range(300001)]

for i in range(300001):
    if i % 7 == 1 or i % 7 == 6:
        this_prime_num[i] = 1
for i in range(2, 300001):
    j = i * 2
    while this_prime_num[i] == 1 and  j < len(this_prime_num):
        
        this_prime_num[j] = 0
        j += i


this_primenum_list = []
for i in range(2, len(this_prime_num)):
    if this_prime_num[i]:
        this_primenum_list.append(i)

ans_list = []
while True:
    n = int(input())
    if n == 1:
        break
    i = 0
    ans = [n]
    while this_primenum_list[i] <= n:
        
        if n % this_primenum_list[i] == 0:
            ans.append(this_primenum_list[i])
        i += 1
        if i >= len(this_primenum_list):
            break
    ans_list.append(ans)

for i in ans_list:
    print(str(i[0]) + ":", end = "")
    for j in i[1:]:
        print("", end = " ")
        print(j, end = "")
    print()

Solution (Python):
S = [0 for i in range(300000)]
S2 = []
A = [-1, 1]
for i in range(1, int(300000 / 7) + 1):
    d = 7 * i
    for a in A:
        da = d + a
        if da < 300000 and S[da] == 0:
            S2.append(da)
            for j in range(2, int(300000 / 2)):
                if da * j >= 300000:break
                S[da * j] = -1
while 1:
    n = int(input())
    if n == 1:break
    
    
    print(str(n) + ':',' '.join([str(x) for x in S2 if n % x == 0 and x <= n]))

Solution (Python):
S = [0 for i in range(300000)]
S2 = []
A = [-1, 1]
for i in range(1, int(300000 / 7) + 1):
    d = 7 * i
    for a in A:
        da = d + a
        if da < 300000 and S[da] == 0:
            S2.append(da)
            for j in range(2, int(300000 / 2)):
                if da * j >= 300000:break
                S[da * j] = -1
while 1:
    n = int(input())
    if n == 1:break
    print(str(n) + ':',' '.join([str(x) for x in S2 if n % x == 0 and x <= n]))

Solution (Python):



import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        p = self.sieve(300001)
        while True:
            n = input()
            if n == 1:
                break
            ans = '{0}: '.format(n)
            seq = []

            for i in range(len(p)):
                if n % p[i] == 0:
                    seq.append(str(p[i]))

            ans += ' '.join(seq)
            print ans
                    
        return None
    
    def mark(self, s, x):
        for i in xrange(x + x, len(s), x):
            s[i] = False

    def sieve(self, n):
        s = [True] * n
        for x in xrange(n):
            if x % 7 != 1 and x % 7 != 6:
                s[x] = False
        for x in xrange(2, int(n ** 0.5) + 1):
            if s[x]:
                self.mark(s, x)
        return [i for i in xrange(n) if s[i] and i > 1]

if __name__ == '__main__':
    m = Main()
    m.solve()

Solution (Python):
import sys
def sieve (n):
	ms_sieve = [0,0,0,0,0,0]
	ms_sieve += [1 for i in range(n-5)]
	ms_prime = []
	d = 6
	while d <= n:
		if ms_sieve[d] == 0:
			d += 1
			continue
		if d % 7 != 1 and d % 7 != 6:
			ms_sieve[d] = 0
			d += 1
			continue
		ms_prime.append(d)
		prod = 2
		while d * prod <= n:
			ms_sieve[d*prod] = 0
			prod += 1
		d += 1
	return ms_prime
ms_prime = sieve(300000)
while 1:
	n = int(raw_input())
	if n == 1:
		break
	sys.stdout.write("%d:" % n)
	for msp in ms_prime:
		if msp > n:
			break
		quot, rem = divmod(n,msp)
		if rem != 0:
			continue 
		rem2 = quot % 7
		if rem2 == 1 or rem2 == 6: 
			sys.stdout.write(" %d" % msp)
	print ""

Solution (Python):



def monsat(num):
    L = [False for i in range(num+1)]
    for i in range(0,num,7):
        if i == 1 or i == 0:
            continue
        for d in [-1,1]:
            if L[i+d] == False:
                L[i+d] = True
                for j in range((i+d)*2,num,i+d):
                    if L[j] is False:
                        L[j] = [i+d]
                    else:
                        L[j].append(i+d)
    return L

L = monsat(3*10**5+1)
while True:
    n = int(input())
    if n == 1:
        break
    print(str(n) + ':',n if L[n] is True else ' '.join(map(str,L[n])))

Solution (Python):
p = [1]*300003
p[0] = p[1] = 0
for i in xrange(2,300003):
    if p[i] and i%7 == 1 or i%7 == 6:
        p[2*i::i] = [0]*len(p[2*i::i])
    else:
        p[i] = 0
primes = [i for i in xrange(2,300003) if p[i]]

while 1:
    N = int(raw_input())
    if N == 1: break
    ans = []
    for prime in primes:
        if prime > N: break
        if N%prime == 0: ans.append(prime)
    print "%d: %s"%(N," ".join(map(str,ans)))

Solution (Python):
p = [1]*300003
p[0] = p[1] = 0
for i in xrange(2,300003):
    if p[i] and i%7 in (1,6):
        p[2*i::i] = [0]*len(p[2*i::i])
    else:
        p[i] = 0
prime = [i for i in xrange(2,300003) if p[i]]

while 1:
    N = int(raw_input())
    if N == 1: break
    ans = [p for p in prime if N%p == 0]
    print "%d: %s"%(N," ".join(map(str,ans)))

Solution (Python):
from bisect import *
p = [1]*300003
p[0] = p[1] = 0
for i in xrange(2,300003):
    if p[i] and i%7 in (1,6):
        p[2*i::i] = [0]*len(p[2*i::i])
    else:
        p[i] = 0
p = [i for i in xrange(2,300003) if p[i]]

while 1:
    N = int(raw_input())
    if N == 1: break
    ans = [i for i in p[:bisect(p,N+1)] if N%i == 0]
    print "%d: %s"%(N," ".join(map(str,ans)))

Solution (Python):


from bisect import *

Max = 300000
p_c = [True]*Max
p_c[0:2] = [False]*2
for i in range(2, Max):
    if i%7 in (1,6):
        p_c[i*2::i] = [False]*len(p_c[i*2::i])
    else:
        p_c[i] = False
prime = [i for i in range(Max) if p_c[i] == True]

while True:
    n = int(raw_input())
    if n==1: break
    ans = [i for i in prime[:bisect(prime, n+1)] if n%i == 0]
    print str(n) + ':' + ' ' + ' '.join(map(str, ans))

Solution (Python):
import math

def checkifprime(NN):
    for i in range(len(MSprime)):
        if MSprime[i]>NN:
            break
        elif NN%MSprime[i]==0:
            return -1
    return NN


nummax=int(50000)
MSall=sorted([7*x-1 for x in range(1,nummax/7)]+[7*x+1 for x in range(1,nummax/7)])
MSprime=[]
smax=math.sqrt(nummax)
i=6
while i<=smax:
    for x in MSall:
        if x%i==0:
            MSall.remove(x)
    MSprime.append(i)
    i=MSall[0]
MSprime=MSprime+MSall

while(1):
    N=int(raw_input())
    if N==1:
        break
    else:
        ok=[]
        for i in range(len(MSprime)):
            if MSprime[i]>N:
            	break
            elif N%MSprime[i]==0:
                ok.append(MSprime[i])
                cifp=checkifprime(N/MSprime[i])
                if cifp>0 and cifp!=1:
                    ok.append(cifp)
        if len(ok)==0:
        	ok.append(N)
        ok.sort()
                
        print str(N)+': '+' '.join([str(x) for x in ok])

Solution (Python):
from array import array

size = 300000
s = array('i', range(size + 1))
for i in range(size+1):
    if i % 7 != 1 and i % 7 != 6:
        s[i] = 0
s[1] = 0
sqrtn = int(round(size ** 0.5))
for i in range(6, sqrtn + 1):
    if s[i]:
        s[i * i: size + 1: i] = array('i', [0] * len(range(i*i, size+1, i)))
primes = list(filter(None, s))

while True:
    n = int(input())
    if n == 1: break
    i = 0
    ls = []
    for p in primes:
        if p > n: break
        if n % p == 0:
            ls.append(p)
    print(n, end="")
    print(':', end=" ")
    print(*ls)

Solution (Python):
sieve = [0] * 300001
for i in range(6, 300000, 7):
    sieve[i] = sieve[i+2] = 1

MSprimes = []
for i in range(6, 300000, 7):
    if sieve[i] == 1:
        MSprimes.append(i)
        for j in range(2*i, 300000, i):
            sieve[j] = 0
    if sieve[i+2] == 1:
        MSprimes.append(i+2)
        for j in range(2*(i+2), 300000, i+2):
            sieve[j] = 0

while True:
    N = int(input())
    if N == 1: break
    ansp = [x for x in MSprimes if N % x == 0]
    print('{}: {}'.format(N, ' '.join(map(str, ansp))))

Solution (Python):

import sys

msprime = []
i = 6
MAX = 300000
isprime = [1]*300001
while i*i <= MAX: 
    for p in msprime:
        if i % p == 0:
            break
    else:
        msprime.append(i)
        j = i * 2
        while j <= MAX:
            isprime[j] = 0
            j += i
    if i % 7 == 6:
        i += 2
    else:
        i += 5
else:
    tmp = i

for i in range(tmp,MAX):
    if isprime[i] == 1 and i % 7 in (1,6):
        msprime.append(i)

while True:
    n = int(raw_input())
    if n == 1: break
    fact = []
    for i in msprime:
        if n % i == 0:
            fact.append(i)
    sys.stdout.write(str(n)+":")
    for i in fact:
        sys.stdout.write(" "+str(i))
    print ""

Solution (Python):
a=[0]*6+[1,0,1,0,0,0,0]*42857
p=[]
for i in range(6,300000,7):
    if a[i]:
        p+=[i]
        for j in range(i**2,300000,i):
            a[j]=0
    if a[i+2]:
        p+=[i+2]
        for j in range((i+2)**2,300000,i+2):
            a[j]=0
while 1:
    n=int(input())
    if n==1:break
    b=[x for x in p if n%x==0]
    print('{}: {}'.format(n, ' '.join(map(str, b))))

Solution (Python):
sm = [False for i in range(300001)]
for i in range(6, 300000, 7):
    sm[i] = sm[i+2] = True

msprices = []

for i in range(6, 300000, 7):
    if sm[i]:
        msprices.append(i)
        for j in range(2*i, 300000, i):
            sm[j] = False
    if sm[i+2]:
        msprices.append(i+2)
        for j in range(2 * (i+2), 300000, i+2):
            sm[j] = False

while True:
    N = int(input())
    if N == 1:
        break
    ans = []
    for msp in msprices:
        if N % msp == 0:
            ans.append(msp)
    print(N, end=":")
    for a in ans:
        print(" " + str(a), end="")
    print()

Solution (Python):
import copy
import math

ms = []
for i in range(1, int(300000/7)+1):
    ms.append(i*7-1)
    ms.append(i*7+1)

delete = []
for i, n in enumerate(ms):
    for j, m in enumerate(ms[:int(math.sqrt(len(ms)))+1]):
        if j < i and n % m == 0:
            delete.append(i)
            break

for i in reversed(delete):
    del ms[i]

while True:
    num = input()
    num = int(num)

    if num == 1:
        break

    divisors = []
    for d in ms:
        if num % d == 0:
            divisors.append(str(d))

    output_str = " ".join(divisors)
    print("%d: %s" % (num, output_str))

Solution (Python):
MAXN = 300010
sieve = [1]* MAXN
primes = []
for n in range(7,MAXN,7):
    for m in [n-1,n+1]:
        if sieve[m] == 0: continue
        primes.append(m)
        for l in range(2*m,MAXN,m):
            sieve[l] = 0

def solve(n):
    ret = []
    for p in primes:
        if p > n: break
        if n%p == 0:
            ret.append(p)
    return ret

while True:
    N = int(input())
    if N == 1: break
    ans = ' '.join(list(map(str,solve(N))))
    print('{0}: {1}'.format(N,ans))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, m):
            if not a[i]:
                continue
            if not (i % 7 == 1 or i % 7 == 6):
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = []
        for c in self.T:
            if n < c:
                break
            if n % c == 0:
                d.append(c)
        return d

def main():
    rr = []

    pr = Prime(300000**2)

    while True:
        n = I()
        if n == 1:
            break

        d = pr.division(n)
        rr.append('{}: {}'.format(n,' '.join(map(str,d))))

    return '\n'.join(map(str, rr))


print(main())

Solution (Python):
N = 300000
a = [((i % 7 ==1)or(i % 7 ==6)) for i in range(N)]

a[1]=0
p =[]
for i in range(6,N):
    if a[i]:
        p+=[i]
        for j in range(i * i ,N,i):
            a[j] = 0
 
while True:
    n = int(input())
    if n == 1:
        break
    print(n,end = ":")
    for x in p:
        if n % x ==0:
            print(" "+str(x),end = "") 

    print()

Solution (Python):

sieve = [0, 1, 0, 0, 0, 0, 1]*42858

for i in range(2, len(sieve)):
    if sieve[i] == 1:
        for j in range(2*i, len(sieve), i):
            sieve[j] = 0

smP = [i for i, s in enumerate(sieve) if s][1:]

N = int(input())
while N != 1:
    ans = []
    for p in smP:
        if N%p == 0:
            ans.append(p)
    print("{}: {}".format(N, " ".join(map(str, ans))))
    N = int(input())

Solution (Python):
import sys

MAX = 300001
candidate =[0 for i in xrange(MAX)]

for i in xrange(MAX):
    if i % 7 == 1 or i % 7 == 6:
        candidate[i] = 1

prime = []
for i in xrange(2, MAX):
    if candidate[i] == 1:
        prime.append(i)
        temp = i * 2
        while temp < MAX:
            candidate[temp] = 0
            temp += i

while True:
    n = int(sys.stdin.readline())
    if n == 1:
        break
    div = set()
    for p in prime:
        if n < p:
            break
        while n % p == 0:

            div.add(p)
            break
    l_div = list(div)
    l_div.sort()
    print '{}:'.format(n),
    for d in l_div:
        print d,
    print

Solution (Python):
import math
N=300000
L=[False]*(N+1)
for i in range(1,N):
    t=i%7
    if t==6 or t==1:
        L[i]=True
for i in range(2,int(math.sqrt(N))):
    if L[i]==True:
        j=2
        while i*j<=N:
            L[i*j]=False
            j+=1
L=[i for i in range(len(L)) if L[i]==True]

while True:
    n=input()
    if n==1:break
    ans=[str(i) for i in L[1:] if n%i==0]
    print "%d: %s"%(n," ".join(ans))

Solution (Python):
"""
Problem B: 月曜土曜素因数
https://onlinejudge.u-aizu.ac.jp/problems/1154
1 <= n <= 300000
"""
def solve(n, mspf):
    ans = []
    for i in mspf:
        if n < i: break
        if n % i == 0:
            ans.append(i)
    return ans

if __name__ == '__main__':
    """
    1. 1~300000までの月曜土曜素数を取得
    2. if n ％(月曜土曜素数) == 0: appendで月曜土曜素因数を取得
    """
    MAX = 300001
    check = [True]*MAX
    mspf = []

    for i in range(7,MAX,7):
        for j in [i-1, i+1]:
            if check[j]:
                mspf.append(j)
            for k in range(2*j, MAX, j):
                check[k] = False

    while(True):
        n = int(input())
        if n == 1:
            exit()
        ans = solve(n, mspf)
        ans_txt = " ".join(list(map(str,ans)))
        print("{0}: {1}".format(n, ans_txt))

Solution (Python):
def ms_number(n):
    count = 1
    msnumber_list = [6]
    while msnumber_list[-1] < n:
        msnumber_list.append(7 * count + 1)
        msnumber_list.append(7 * count + 6)
        count += 1

    return msnumber_list[:-1]


def ms_prime(n, msnumber_list):
    msprime_list = []
    msprime_flag = [0 for i in range(n + 1)]

    for i in msnumber_list:
        if msprime_flag[i] == 0:
            msprime_list.append(i)
            for j in msnumber_list:
                if i * j > n:
                    break
                msprime_flag[i * j] = 1

    return msprime_list


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    divisors.sort()
    return divisors


msnumber_list = ms_number(300000)
msprime_list = ms_prime(300000, msnumber_list)

answer = []
input_list = []

while True:
    n = int(input())
    if n == 1:
        break

    input_list.append(n)
    divisors = make_divisors(n)

    answer.append([d for d in divisors if d in msprime_list])


for i in range(len(input_list)):
    print(str(input_list[i]) + ": ", end="")
    print(*answer[i])

Solution (Python):
def prime_factor(N):
    lists = [N]
    for i in range(2, int(N ** 0.5) + 1):
        if N % i == 0:
            lists.append(i)
            lists.append(N // i)
    lists.sort()  
    return lists

ans = []
Nlist = []

while True:
    N = int(input())
    if N == 1:
        break
    Nlist.append(N)

    MSprime = []
    for i in prime_factor(N):
        bool_append = True
        if i % 7 in [1, 6]:
            for j in MSprime:
                if not i % j:
                    bool_append = False
                    break
            
            if bool_append:
                MSprime.append(i)
    
    ans.append(MSprime)
    
for i in range(len(ans)):
    print(str(Nlist[i]) + ':', end='')    
    for j in range(len(ans[i])):
        print(' ' + str(ans[i][j]), end='')
    print()

Solution (Python):
def modifiedSieve():
    L = 300001
    msPrimes = []
    isMSPrime = [ True for _ in range(L) ]
    for i in range(6):
        isMSPrime[i] = False
    for i in range(6, L):
        if isMSPrime[i]:
            if i % 7 == 1 or i % 7 == 6:
                msPrimes.append(i)
                for j in range(i * i, L, i):
                    isMSPrime[j] = False
            else:
                isMSPrime[i] = False
    return msPrimes

def getMSFactors(num, msPrimes):
    factors = set()
    for msp in msPrimes:
        if msp > num:
            break
        if num % msp == 0:
            factors.add(msp)
    if num in msPrimes:
        factors.add(num)
    return sorted(list(factors))

if __name__ == '__main__':
    msPrimes = modifiedSieve()
    while True:
        num = int(input())
        if num == 1:
            break
        
        factors = getMSFactors(num, msPrimes)
        print("{}: {}".format(num, " ".join(list(map(str, factors)))))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

koho = [6]
i = 1
while True:
    koho.append(i*7+1)
    koho.append(i*7+6)
    if i*7 > 300005:
        break
    else:
        i += 1

prime = []
limit = math.sqrt(koho[-1])
while True:
    p = koho[0]
    if limit <= p:
        prime = prime + koho
        break
    else:
        prime.append(p)
        koho = [e for e in koho if e%p != 0]


while True:
    N = inp()
    if N == 1:
        break
    else:
        ans = []
        for p in prime:
            if N%p == 0:
                ans.append(p)
        print(str(N)+':',' '.join(map(str,ans)))

Solution (Python):
p = [1]*300010
p[0]=p[1]=0
for i in range(2, 300010):
  if not(i%7==1 or i%7==6):
    p[i] = 0

for i in range(2, 300010):
  if p[i]:
    for j in range(i*2, 300010, i):
      p[j] = 0

doyososu = []
for i in range(2, 300010):
  if p[i]:
    doyososu.append(i)

while True:
  n = int(input())
  if n==1:
    break
  ans = []
  for e in doyososu:
    if n%e==0:
      ans.append(e)
  print(n, ":", sep="", end=" ")
  print(*ans)

Solution (Python):
from math import sqrt
A = []
for i in range(2,300000):
    if i%7==1 or i%7==6:
        k = 1
        for j in A:
            if j>sqrt(i):
                break
            elif i%j==0:
                k = 0
                break
        if k==1:
            A.append(i)
while True:
    n = int(input())
    if n==1:
        break
    a = n
    ans = []
    for b in A:
        if a%b==0:
            ans.append(b)
        if a<b:
            break
    print(str(n)+":",end=" ")
    print(*ans)

Solution (Python):
check = [True]*(3*10**5+1)
pri = []
for i in range(6,3 * 10 ** 5 + 1):
    if (i % 7 == 1 or i % 7 == 6) and check[i]:
        pri.append(i)
        for k in range(i * 2, 3 * 10 ** 5 + 1, i):
            check[k] = False

def main(n):
    res = ["{}:".format(n)]
    for p in pri:
        if n % p == 0:
            res.append(str(p))
    print(" ".join(res))
while 1:
    n = int(input())
    if n == 1:
        break
    main(n)

Solution (Python):
from math import floor


def divisor(n):
    left = [1]
    right = [n]
    sup = floor(pow(n,1/2))
    for p in range(2,sup+1):
        if n % p == 0:
            if p == n//p:
                left.append(p)
                continue
            left.append(p)
            right.append(n//p)
    res = left + right[::-1]
    return res

ans_list = []

def main():
    while True:
        ans = solve()
        if ans == "end":
            break
        ans_list.append(ans)
    
    for ans in ans_list:
        print(ans)

def solve():
    n = int(input())
    if n == 1:
        return "end"
    cand = [c for c in divisor(n) if c % 7 in (1,6)]
    ans = "{}:".format(n)
    for c in cand:
        flag = True
        for p in [p for p in divisor(c) if p % 7 in (1,6)]:
            if p not in (1,c):
                flag = False
                break
        if c > 1 and flag is True:
            ans += " {}".format(c)
    return ans

main()

Solution (Python):
def main():
    while True:
        data = int(input())
        if data == 1: break

        i = 1
        factlist = []
        while True:
            item = 7 * i - 1
            if item > int(data / 6) + 1: break

            if data % item == 0:
                quo = int(data / item)
                if isms(quo) and ismsp(quo):
                    factlist.append(quo)
            

            item = 7 * i + 1
            if item > int(data / 6) + 1:break

            if data % item == 0:
                quo = int(data / item)
                if isms(quo) and ismsp(quo):
                    factlist.append(quo)

            i += 1

        factlist.sort()
        if factlist == []: factlist.append(data)

        print(str(data) + ":", end = "")

        for item in factlist:
            print(" " + str(item), end = "")
        print("")
            

def isms(num):
    if num % 7 == 1 or num % 7 == 6: return True
    else: return False

def ismsp(num):
    i = 1
    while True:
        item = 7 * i - 1
        if item > int(num / 6) + 1: break

        if num % item == 0: return False

        item = 7 * i + 1
        if item > int(num / 6) + 1: break

        if num % item == 0: return False

        i += 1
    return True
main()

Solution (Python):
a = [0]*6+[1,0,1,0,0,0,0]*42857
p=[]
for i in range(6,300000,7):
    if a[i]:
        p.append(i)
        for j in range(i**2,300000,i):
            a[j]=0
    if a[i+2]:
        p.append(i+2)
        for j in range((i+2)**2,300000,i+2):
            a[j]=0

while True:
    n=int(input())
    if n==1:
        break
    ans = "{}:".format(n)
    for i in p:
        if n%i==0:
            ans += " {}".format(i)
    print(ans)

Solution (Python):

isgdprime=[1 for i in range(300001)]
gdprimes=[]
for i in range(6):
    isgdprime[i]=0
for i in range(300001):
    if isgdprime[i]==1 and (i%7==1 or i%7==6):
        gdprimes.append(i)
        j=i*2
        while j<300001:
            isgdprime[j]=0
            j+=i
    else:
        isgdprime[i]=0

while 1:
    n=int(input())
    if n==1:
        break
    print(n,end=':')
    for i in range(len(gdprimes)):
        if n%gdprimes[i]==0:
            print('',gdprimes[i],end='')
    print()