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 7N+{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 ax = 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 &times; 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 &times; 6 &times; 6 = 8 &times; 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



Sample input:
205920
262144
262200
279936
299998
1


Sample output:
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

Submission status: Wrong Answer

Solution code:
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):
        #print(j)
        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)
print(this_primenum_list[:30])
ans_list = []
while True:
    n = int(input())
    if n == 1:
        break
    i = 0
    ans = [n]
    while this_primenum_list[i] <= n:
        #print(i)
        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()

Submission status: Wrong Answer

Solution code:
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 = []
    n = N
    for p in prime:
        if p > n: break
        if n%p == 0:
            ans.append(p)
            while n%p == 0: n /= p
    print "%d: %s"%(N," ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
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:
                    ok.append(cifp)
        if len(ok)==0:
        	ok.append(N)
        ok.sort()
                
        print str(N)+': '+' '.join([str(x) for x in ok])

Submission status: Time Limit Exceeded

Solution code:
S = [0 for i in range(300000)]
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:
            S[da] = 1
            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
    res = [str(n) + ':']
    for i in range(2, n+1):
        if S[i] == 1 and n % i == 0:
            res.append(str(i))

    print(' '.join(res))

Submission status: Time Limit Exceeded

Solution code:
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(str(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
    res = [str(n) + ':']
    res += [x for x in S2 if int(x) <= n and n % int(x) == 0]
    print(' '.join(res))

Submission status: Time Limit Exceeded

Solution code:
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(str(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
    #res = [str(n) + ':']
    #res += [x for x in S2 if int(x) <= n and n % int(x) == 0]
    print(str(n) + ':',' '.join([x for x in S2 if int(x) <= n and n % int(x) == 0]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
def sieve (n):
	ms_prime = [0,0,0,0,0,0]
	ms_prime += [1 for i in range(n-5)]
	ub = math.sqrt(n) + 1
	d = 6
	while d <= ub:
		if ms_prime[d] == 0:
			d += 1
			continue
		if d % 7 != 1 and d % 7 != 6:
			ms_prime[d] = 0
			d += 1
			continue
		prod = 2
		while d * prod <= n:
			ms_prime[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)
	msp_factor = set()
	for i in range(6, n+1):
		tmp_factor = 0
		if ms_prime[i] == 1 and n % i == 0 and ((n / i) % 7 == 1 or (n / i) % 7 == 6): 
			sys.stdout.write(" %d" % i)
	else :
		print ""

Submission status: Time Limit Exceeded

Solution code:
import math

nummax=300000
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(MSall[-1])
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=[]
        i=0
        while MSprime[i]<=N:
            if N%MSprime[i]==0:
                ok.append(MSprime[i])
            i=i+1
        print str(N)+': '+' '.join([str(x) for x in ok])

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
msprime = []
i = 6
MAX = 300000
while i <= MAX:
    for p in msprime:
        if i % p == 0:
            break
    else:
        msprime.append(i)
        j = i * 2
    if i % 7 == 6:
        i += 2
    else:
        i += 5
print msprime

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

Submission status: Time Limit Exceeded

Solution code:
def factors(n):
    sieve = [1]*(n+10)
    m = 1
    while m*7-1 <= n:
        for p in [m*7-1,m*7+1]:
            if sieve[p] == 0: continue
            for pp in range(2*p,n+1,p):
                sieve[pp] = 0
        m += 1
    ret = []
    m = 1
    while m*7-1 <= n:
        for p in [m*7-1,m*7+1]:
            if sieve[p] and n % p == 0:
                ret.append(p)
        m += 1
    return(ret)

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

Submission status: Time Limit Exceeded

Solution code:
def factors(n):
    sieve = [1]*(n+10)
    ret = []
    m = 1
    while m*7-1 <= n:
        for p in [m*7-1,m*7+1]:
            if sieve[p] == 0: continue
            if n%p == 0:
                ret.append(p)
            for pp in range(2*p,n+1,p):
                sieve[pp] = 0
        m += 1
    return(ret)

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

Submission status: Accepted

Solution code:
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):
        #print(j)
        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)
#print(this_primenum_list[:30])
ans_list = []
while True:
    n = int(input())
    if n == 1:
        break
    i = 0
    ans = [n]
    while this_primenum_list[i] <= n:
        #print(i)
        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()

Submission status: Accepted

Solution code:
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
    #res = [str(n) + ':']
    #res += [x for x in S2 if int(x) <= n and n % int(x) == 0]
    print(str(n) + ':',' '.join([str(x) for x in S2 if n % x == 0 and x <= n]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

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()

Submission status: Accepted

Solution code:
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 ""

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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])))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))))

Submission status: Accepted

Solution code:
#coding: utf-8
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 ""

Submission status: Accepted

Solution code:
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))))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
N = 300000
a = [((i % 7 ==1)or(i % 7 ==6)) for i in range(N)]
#print(a[11])
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()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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())

Submission status: Accepted

Solution code:
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:
#            n /= p
            div.add(p)
            break
    l_div = list(div)
    l_div.sort()
    print '{}:'.format(n),
    for d in l_div:
        print d,
    print

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
"""
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)))))

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)