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

Solution code:
from math import floor
# 約数全列挙(ソート済み)
# n = 24 -> [1,2,3,4,6,8,12,24]
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()

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Runtime Error

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: WA: Presentation Error

Solution code:
#coding: utf-8
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)
    print str(n)+":",
    for i in fact:
        print i,
    print ""

Submission status: WA: Presentation Error

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(a, end=" ")
    print()

Submission status: WA: Presentation Error

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: WA: Presentation Error

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(x,end = " ")

    print()