Problem:
 Score : 800 points    Problem Statement You are given a polynomial of degree N with integer coefficients: f(x)=a_Nx^N+a_{N-1}x^{N-1}+...+a_0 . Find all prime numbers p that divide f(x) for every integer x .      Constraints  0 \leq N \leq 10^4  |a_i| \leq 10^9(0\leq i\leq N)  a_N \neq 0  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  a_N  :  a_0       Output Print all prime numbers p that divide f(x) for every integer x , in ascending order.        Sample Input 1 2
7
-7
14      Sample Output 1 2
7  2 and 7 divide, for example, f(1)=14 and f(2)=28 .       Sample Input 2 3
1
4
1
5      Sample Output 2  There may be no integers that satisfy the condition.       Sample Input 3 0
998244353      Sample Output 3 998244353

Solution (Python):
import sys,math

def I(): return int(sys.stdin.readline().rstrip())

N = I()
a = [I() for _ in range(N+1)]
a.reverse()

ans = set([])

g = a[0]
for i in range(N):
    g = math.gcd(g,a[i+1])

for p in range(2,int(g**.5)+1):
    if g % p == 0:
        ans.add(p)
        g //= p
if g != 1:
    ans.add(g)

if N == 0:
    ans = list(ans)
    ans.sort()
    print(*ans, sep='\n')
    exit()


def sieve_of_eratosthenes(n):
    prime_list = []  
    A = [1]*(n+1)    
    A[0] = A[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if A[i]:
            prime_list.append(i)
            for j in range(i**2,n+1,i):
                A[j] = 0
    for i in range(math.floor(math.sqrt(n))+1,n+1):
        if A[i] == 1:
            prime_list.append(i)
    return prime_list


prime_list = sieve_of_eratosthenes(N)

for p in prime_list:  
    if a[0] % p != 0:
        continue
    else:
        for i in range(p-1):
            if i == 0:
                r = 0
                for j in range(p-1,N+1,p-1):
                    r += a[j]
                    r %= p
                if r != 0:
                    break
            else:
                r = 0
                for j in range(i,N+1,p-1):
                    r += a[j]
                    r %= p
                if r != 0:
                    break
        else:
            ans.add(p)

ans = list(ans)
ans.sort()
print(*ans,sep='\n')

Solution (Python):
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def Ind(b,n):
    count=0
    while n%b==0:
        count+=1
        n//=b
    return count

prime=get_sieve_of_eratosthenes_new(10**4+1)

from fractions import gcd

N=int(input())
a=[]
for i in range(N+1):
    a.append(int(input()))

a=a[::-1]
ans=set([])
for p in prime:
    data=[0 for i in range(p)]
    for i in range(1,N+1):
        data[(i-1)%(p-1)]+=a[i]%p
        data[(i-1)%(p-1)]%=p
    check=(a[0]%p==0)
    for i in range(p):
        check=check&(data[i]%p==0)
    if check:
        ans.add(p)


n=a[0]
for i in range(N+1):
    n=gcd(n,a[i])

prime=get_sieve_of_eratosthenes_new(32000)

for p in prime:
    i=Ind(p,n)
    if i!=0:
        ans.add(p)
    n//=pow(p,i)

if abs(n)!=1:
    ans.add(abs(n))

ans=list(ans)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

Solution (Python):
def f(n):
  a=[];f=2
  while f*f<=n:
    if n%f==0:a.append(f);n//=f
    else:f+=1
  if n!=1:a.append(n)
  return set(a)
s=[2];n=int(input())
for L in range(3,n+1):
  c=True
  for M in s:
    if L%M==0:c=False
  if c==True:s.append(L)
A=[int(input())for i in range(n+1)]
P=sorted(list(set(s)|f(abs(A[0]))))
for p in P:
  B=A[0:n+2];b=0
  for j in range(n+1):
    if p+j<n+1:B[j+p-1]=(B[j+p-1]+B[j])%p
    elif B[j]%p!=0:b=1;break
  if b==0:print(p)

Solution (Python):
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

sosuu=[2];n=int(input())
for L in range(3,n+100):
    chk=True
    for L2 in sosuu:
        if L%L2 == 0:chk=False
    if chk==True:sosuu.append(L)
S=set(sosuu)



A=[0]*(n+1)
g=0
for i in range(n+1):
  A[i]=int(input())
P=[]
PP=factorization(abs(A[0]))
for i in range(len(PP)):
  P.append(PP[i][0])
if P==[1]:
  P=[]
P=set(P)
P=S|P
P=list(P)
P.sort()
for i in range(len(P)):
  p=P[i]
  B=A[0:n+2]
  b=0
  for j in range(n+1):
    if p+j<n+1:
      B[j+p-1]=(B[j+p-1]+B[j])%p
    else:
      if B[j]%p!=0:
        b=1
        break
  if b==0:
    print(p)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
from fractions import gcd

N = int(input())
A = np.array([input() for _ in range(N+1)], dtype=np.int64)[::-1]





U = int(10 ** 4.5 + 10)
is_prime = np.zeros(U+1, dtype = np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(U+1):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::2*p] = 0
primes = is_prime.nonzero()[0]

div = primes[A[N] % primes == 0]

cand = set(div)
x = abs(A[N])
for p in cand:
    while x % p == 0:
        x //= p
if x != 1:
    cand.add(x)

cand |= set(primes[primes <= N].tolist())
cand = sorted(cand)

def test(p):
    if A[0] % p != 0:
        return False
    
    if p > N+10:
        return (A % p == 0).all()
    B = np.pad(A,[0,(-N-1)%(p-1)],'constant').reshape(-1,p-1).sum(axis = 0)
    return (B % p == 0).all()

answer = '\n'.join(str(p) for p in cand if test(p))
print(answer)

Solution (Python):
n = int(input())
a = list(reversed([int(input()) for i in range(n+1) ]))

prime = [2,3]

for i in range(5,100000):
    f = True
    for p in prime:
        if(p*p > i):break
        if i % p == 0 :
            f = False
            break
    if f :prime.append(i)

def gcd(x,y):
    if(x < y): x,y = y,x
    if(y == 0): return x
    return gcd(y,x % y)

def isprime(x):
    f = True
    for p in prime:
        if(p*p > x):break
        if x % p == 0:
            f = False
            break
    return f

g = 0
for i in a:
    g = gcd(abs(i),g)



for p in prime:
    if (p > n+1):break
    m = [0 for i in range(p-1)]
    if a[0] % p != 0:continue
    for i in range(n+1):
        m[i % (p-1)] += (a[i] % p)
    f = True
    for i in m:
        if i % p > 0 :
            f = False
            break    
    if f:print(p)




for p in prime:
    if g == 1:break
    if(g % p == 0):
        g //= p
        if (p > n+1):print(p)

if(g != 1):
    if isprime(g):print(g)

Solution (Python):
import sys
from fractions import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
x = 0
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
ps = []

i = 2
while i**2 <= m and i <= n+1:
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1
if m != 1 and n != 0:
	ps.append(m)
g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))

ans = []
i = 2
while i**2 <= g:
	if g%i == 0:
		if i >= n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1 and g >= n+1:
	ans.append(g)

a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			ans.append(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				ans.append(p)
ans = sorted(list(set(ans)))
if ans:
	print(*ans, sep="\n")

Solution (Python):
import sys
from fractions import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
x = 0
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
ps = []

i = 2
while i**2 <= m and i <= n+1:

	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1
if m != 1 and n != 0:
	ps.append(m)

g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))


ans = []

i = 2
while i**2 <= g:

	if g%i == 0:
		if i >= n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1 and g >= n+1:
	ans.append(g)

a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			ans.append(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				ans.append(p)
ans = sorted(list(set(ans)))
if ans:
	print(*ans, sep="\n")

Solution (Python):
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret

def eratosthenes(N):
    if N == 0:
        return []
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret

N = int( input())
A = [ int( input()) for _ in range(N+1)]
Primes = eratosthenes(N)
ANS = []
F = factors( abs(A[0]))
for f in F:
    if f >= N+1:
        Primes.append(f)
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1): 
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*(p-1)
        for i in range(N+1): 
            poly[(N-i)%(p-1)] = (poly[(N-i)%(p-1)] + A[i])%p
        check = 0
        if sum(poly) == 0 and A[N]%p == 0: 
            check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Solution (Python):
import sys
from fractions import gcd


def eratosthenes_generator():
    yield 2
    n = 3
    h = {}
    while True:
        m = n
        if n in h:
            b = h[n]
            del h[n]
        else:
            b = n
            yield n
        m += b << 1
        while m in h:
            m += b << 1
        h[m] = b
        n += 2


def prime(n):
    ret = []
    for i in eratosthenes_generator():
        if n % i == 0:
            ret.append(i)
            while n % i == 0:
                n = n // i
        if n == 1 or i * i > n:
            break
    if n > 1:
        ret.append(n)
    return ret


def solve(n, aaa):
    g = abs(aaa[-1])
    for a in aaa[:-1]:
        if a != 0:
            g = gcd(g, abs(a))
    ans = set(prime(g))

    for p in eratosthenes_generator():
        if p > n + 2:
            break
        if p in ans or aaa[0] % p != 0:
            continue
        q = p - 1
        if all(sum(aaa[i::q]) % p == 0 for i in range(q)):
            ans.add(p)

    ans = sorted(ans)
    return ans


n = int(input())
aaa = list(map(int, sys.stdin))
aaa.reverse()
print('\n'.join(map(str, solve(n, aaa))))

Solution (Python):
import sys
from fractions import gcd


def eratosthenes_generator():
    yield 2
    n = 3
    h = {}
    while True:
        m = n
        if n in h:
            b = h[n]
            del h[n]
        else:
            b = n
            yield n
        m += b << 1
        while m in h:
            m += b << 1
        h[m] = b
        n += 2


def prime(n):
    ret = []
    for i in eratosthenes_generator():
        if n % i == 0:
            ret.append(i)
            while n % i == 0:
                n = n // i
        if n == 1 or i * i > n:
            break
    if n > 1:
        ret.append(n)
    return ret


def solve(n, aaa):
    g = abs(aaa[-1])
    for a in aaa[:-1]:
        if a != 0:
            g = gcd(g, abs(a))
    ans = set(prime(g))

    for p in eratosthenes_generator():
        if p > n + 2:
            break
        if p in ans or aaa[0] % p != 0:
            continue
        q = p - 1
        tmp = [0] * q
        for i, a in enumerate(aaa):
            tmp[i % q] += a
        if all(t % p == 0 for t in tmp):
            ans.add(p)

    ans = sorted(ans)
    return ans


n = int(input())
aaa = list(map(int, sys.stdin))
aaa.reverse()
print('\n'.join(map(str, solve(n, aaa))))

Solution (Python):
import sys
from fractions import gcd


def eratosthenes_generator():
    yield 2
    n = 3
    h = {}
    while True:
        m = n
        if n in h:
            b = h[n]
            del h[n]
        else:
            b = n
            yield n
        m += b << 1
        while m in h:
            m += b << 1
        h[m] = b
        n += 2


def prime(n):
    ret = []
    if n % 2 == 0:
        ret.append(2)
        while n % 2 == 0:
            n >>= 1
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            ret.append(i)
            while n % i == 0:
                n = n // i
        if n == 1:
            break
    if n > 1:
        ret.append(n)
    return ret


def solve(n, aaa):
    g = abs(aaa[-1])
    for a in aaa[:-1]:
        if a != 0:
            g = gcd(g, abs(a))
    ans = set(prime(g))

    for p in eratosthenes_generator():
        if p > n + 2:
            break
        if p in ans or aaa[0] % p != 0:
            continue
        q = p - 1
        tmp = [0] * q
        for i, a in enumerate(aaa):
            tmp[i % q] += a
        if all(t % p == 0 for t in tmp):
            ans.add(p)

    ans = sorted(ans)
    return ans


n = int(input())
aaa = list(map(int, sys.stdin))
aaa.reverse()
print('\n'.join(map(str, solve(n, aaa))))

Solution (Python):
def e_polynominal_divisors(N, A):
    
    from fractions import gcd

    def prime_factorization_dict(n):
        """nを素因数分解したときの素数とその指数の辞書"""
        i, table = 2, {}
        while i**2 <= n:
            table[i] = 0
            while n % i == 0:
                table[i] += 1
                n //= i
            if table[i] == 0:
                table.pop(i)
            i += 1
        if n > 1:
            table[n] = 1
        return table

    def prime_table(n):
        """n以下の素数のリスト(エラトステネスの篩)"""
        if n == 0:
            return []
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False  
        for j in range(2, int(n**0.5) + 1):
            if not is_prime[j]:
                continue
            for k in range(j * 2, n + 1, j):
                is_prime[k] = False  
        return [i for i in range(n + 1) if is_prime[i]]

    
    
    
    g = abs(A[N])
    for a in A:
        if a != 0:
            g = gcd(g, abs(a))
    ans = list(prime_factorization_dict(g).keys())

    a = A[::-1]  
    
    
    
    
    for p in prime_table(N):
        c = [0] * p
        for d in range(p):
            c[d] = a[d] % p
        
        for d in range(p, N + 1):
            r = d % (p - 1)
            if r == 0:
                r = p - 1
            c[r] = (c[r] + a[d]) % p

        for factor in c:
            if factor != 0:
                break
        else:
            
            ans.append(p)
    ans = sorted(set(ans))
    return '\n'.join(map(str, ans))

N = int(input())
A = [int(input()) for _ in range(N + 1)]
print(e_polynominal_divisors(N, A))

Solution (Python):
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret

def eratosththenes(N):
    if N == 0:
        return [0]
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    for i in range(N+1):
        if work[i]:
            for j in range(2* i, N+1, i):
                work[j] = False
    return work


N = int( input())
A = [ int( input()) for _ in range(N+1)]
E = eratosththenes(N)
Primes = [ i for i in range(N+1) if E[i] == 1]
ANS = []
F = factors( abs(A[0]))
for f in F:
    if f >= N+1:
        Primes.append(f)
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1):
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*(p-1)
        for i in range(N+1): 
            poly[(N-i)%(p-1)] = (poly[(N-i)%(p-1)] + A[i])%p
        check = 0
        if sum(poly) == 0 and A[N]%p == 0: 
            check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N+1)]


def factorize(n):
    b = 2
    fct = {}
    while b * b <= n:
        while n % b == 0:
            n //= b
            if b in fct.keys():
                fct[b] += 1
            else:
                fct[b] = 1
        b += 1
    if n > 1:
        fct[n] = 1
    return fct


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


g = abs(A[0])
for a in A:
    g = gcd(g, abs(a))
cand = list(factorize(g).keys())
ans_set = [c for c in cand]


def SieveofEratosthenes(N: int) -> list:
    isPrime = [0] + [1 for _ in range(N-1)]
    numList = [i+1 for i in range(N)]
    for i in range(1, N):
        if isPrime[i] == 1:
            for k in range(i+1, N):
                if (k+1) % (i+1) == 0:
                    isPrime[k] = 0
    returnList = []
    for i, v in enumerate(isPrime):
        if v == 1:
            returnList.append(numList[i])
    return returnList


cand = SieveofEratosthenes(N+1)


def ans(cand):
    for p in cand:
        if A[0] % p != 0:
            continue
        for n in range(1, p):
            cur = 0
            for k in range((N-n)//(p-1)+1):
                cur += A[n+k*(p-1)]
                cur %= p
            if cur != 0:
                break
        if cur == 0:
            ans_set.append(p)
    return ans_set


A.reverse()
ans_set = ans(cand)
ans = sorted(list(set(ans_set)))
for p in ans:
    print(p)

Solution (Python):
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret

def eratosththenes(N):
    if N == 0:
        return [0]
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    for i in range(N+1):
        if work[i]:
            for j in range(2* i, N+1, i):
                work[j] = False
    return work


N = int( input())
A = [ int( input()) for _ in range(N+1)]
E = eratosththenes(N)
Primes = [ i for i in range(N+1) if E[i] == 1]
ANS = []
F = factors( abs(A[0]))
for f in F:
    if f >= N+1:
        Primes.append(f)
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1):
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*(p-1)
        for i in range(N+1):
            poly[(N-i)%(p-1)] = (poly[(N-i)%(p-1)] + A[i])%p
        check = 1
        if sum(poly) != 0 or A[N]%p != 0:
            check = 0
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Solution (Python):
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    i = 1
    divset = set()
    while i * i <= a:
        if a % i == 0: divset |= {i, a//i}
        i += 1
    divset.remove(1)
    return divset

def is_prime(a):
    if a <= 3: 
        prime = [False, False, True, True]
        return prime[a]
    i = 2
    while i * i <= a:
        if a % i == 0: return False
        i += 1
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes_bool = [True] * (N + 1)
primes = []
for p in range(2, N+1):
    if primes_bool[p]:
        primes.append(p)
        p_mult = p * 2
        while p_mult <= N:
            primes_bool[p_mult] = False
            p_mult += p

ans = []
used = set()
gcd_of_A = abs(A[N])
for a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), gcd_of_A)

commondiv = divisor(gcd_of_A)
for d in commondiv:
    if d > 1 and is_prime(d): 
        ans.append(d)
        used |= {d}

for p in primes:
    if A[0] % p == 0:
        for i in range(1, p):
            coefficient = 0
            index_a = i
            while index_a <= N:
                coefficient += A[index_a]
                coefficient %= p
                index_a += p-1
            if coefficient > 0: break
        else:
            if p not in used: ans.append(p)

ans.sort()
for a in ans: print(a)

Solution (Python):
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    i = 1
    divset = set()
    while i * i <= a:
        if a % i == 0: divset |= {i, a//i}
        i += 1
    divset.remove(1)
    return divset

def is_prime(a):
    if a <= 3: 
        prime = [False, False, True, True]
        return prime[a]
    i = 2
    while i * i <= a:
        if a % i == 0: return False
        i += 1
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes_bool = [True] * (N + 1)
primes = []
for p in range(2, N+1):
    if primes_bool[p]:
        primes.append(p)
        p_mult = p * 2
        while p_mult <= N:
            primes_bool[p_mult] = False
            p_mult += p

ans = []
used = set()
gcd_of_A = abs(A[N])
for a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), gcd_of_A)

commondiv = divisor(gcd_of_A)
for d in commondiv:
    if d > 1 and is_prime(d): 
        ans.append(d)
        used |= {d}

for p in primes:
    if A[0] % p == 0:
        for i in range(1, p):
            coefficient = 0
            index_a = i
            while index_a <= N:
                coefficient += A[index_a]
                coefficient %= p
                index_a += p-1
            if coefficient > 0: break
        else:
            if p not in used: ans.append(p)

ans.sort()
for a in ans: print(a)

Solution (Python):
def p_factors(n):
    if n < 2:
        return []
    
    d = 2
    result = []
    while n > 1 and d*d <= n:
        if n % d == 0:
            result.append(d)
        while n % d == 0:
            n //= d
        d += 1
        
    if n > 1:
        
        result.append(n)
    return result

def sieve_of_eratosthenes(ub):
    
    
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return [i for i in range(ub+1) if prime[i]]

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

def gcd_list(lst):
    if len(lst) == 0:
        return 0
    if len(lst) == 1:
        return lst[0]
    g = abs(lst[0])
    for l in lst[1:]:
        g = gcd(g, abs(l))
    return g

N = int(input())
A = [int(input()) for _ in range(N+1)]

cands = set(sieve_of_eratosthenes(N) + p_factors(gcd_list(A)))
answer = []
A = list(reversed(A))

for p in cands:
    flag = True
    
    
    
    
    
    if A[0] % p != 0:
        flag = False
    else:
        for i in range(1, min(N, p-1) + 1):
            h = 0  
            j = i
            while j <= N:
                h = (h + A[j]) % p
                j += p - 1
            if h != 0:
                flag = False
                break
                
    if flag:
        answer.append(p)

if answer:
    answer = sorted(answer)
print(*answer, sep='\n')

Solution (Python):
def p_factors(n):
    if n < 2:
        return []
    
    d = 2
    result = []
    while n > 1 and d*d <= n:
        if n % d == 0:
            result.append(d)
        while n % d == 0:
            n //= d
        d += 1
        
    if n > 1:
        
        result.append(n)
    return result

def sieve_of_eratosthenes(ub):
    
    
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return [i for i in range(ub+1) if prime[i]]

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

def gcd_list(lst):
    if len(lst) == 0:
        return 0
    if len(lst) == 1:
        return lst[0]
    g = abs(lst[0])
    for l in lst[1:]:
        g = gcd(g, abs(l))
    return g

N = int(input())
A = [int(input()) for _ in range(N+1)]

cands = set(sieve_of_eratosthenes(N) + p_factors(gcd_list(A)))
answer = []
A = list(reversed(A))

for p in cands:
    flag = True
    
    
    if A[0] % p != 0:
        flag = False
    else:
        for i in range(1, min(N, p-1) + 1):
            h = 0  
            j = i
            while j <= N:
                h = (h + A[j]) % p
                j += p - 1
            if h != 0:
                flag = False
                break
                
    if flag:
        answer.append(p)

if answer:
    answer = sorted(answer)
print(*answer, sep='\n')

Solution (Python):
def prime_fact(n: int)->list:
    '''n の素因数を返す
    '''
    if n < 2:
        return []

    d = 2
    res = []
    while n > 1 and d * d <= n:
        if n % d == 0:
            res.append(d)
        while n % d == 0:
            n //= d
        d += 1

    if n > 1:
        
        res.append(n)

    return res


def gen_primes(n: int)->int:
    '''n まで(n 含む)の素数を返します。
    '''
    if n < 2:
        return []
    primes = [2]

    if n < 3:
        return primes
    primes.append(3)

    def is_prime(n: int)->bool:
        for p in primes:
            if n % p == 0:
                return False
        return True

    
    
    for k in range((N+1)//6):
        k += 1

        if is_prime(6*k-1):
            primes.append(6*k-1)

        if is_prime(6*k+1):
            primes.append(6*k+1)

    return primes


def gcd(a: int, b: int)->int:
    if a < b:
        a, b = b, a
    return a if b == 0 else gcd(b, a % b)


def gcd_list(A: list)->int:
    if len(A) == 0:
        return 0
    if len(A) == 1:
        return A[0]

    g = abs(A[0])
    for a in A[1:]:
        g = gcd(g, abs(a))
    return g


def polynominal_divisors(N: int, A: list)->list:
    
    A.reverse()
    

    def check(p: int)->bool:
        '''素数 p が任意の整数 x について f(x) を割り切れるかを
        check する。具体的には、

        - a0
        - a1 + ap + a{2p-1} + ...
        - a2 + a{p+1} + a{2p} + ...
        ...
        - a{p-1} + a{2p-2} + ...
        という項が p で割り切れるかを検査する。
        '''
        if A[0] % p != 0:
            return False

        for i in range(1, min(N, p)):
            
            
            
            b = 0
            while i <= N:
                
                b = (b + A[i]) % p
                i += p-1
            if b != 0:
                return False
        return True

    primes = set(gen_primes(N) + prime_fact(gcd_list(A)))
    res = [p for p in primes if check(p)]
    res.sort()

    return res


if __name__ == "__main__":
    N = int(input())
    A = [int(input()) for _ in range(N+1)]

    ans = polynominal_divisors(N, A)
    for a in ans:
        print(a)

Solution (Python):




N = int(input())
a_list = [0]*(N+1)
for i in range(N+1):
    a_list[N-i] = int(input())




primes = list(range(10**5))
primes[0] = 0
primes[1] = 0
for p in range(2, 10**5):
    if primes[p]:
        for i in range(2*p, 10**5, p):
            primes[i] = 0
primes = [p for p in primes if p>0]

p_list_small = [p for p in primes if p <= N]







p_list_large = []
A = abs(a_list[-1])
for p in primes:
    if A % p == 0:
        if p > N:
            p_list_large.append(p)
        while A % p == 0:
            A = A // p
if A != 1:
    p_list_large.append(A)




res_list = []
for p in p_list_small:
    r = 0
    check_list = [0]*(N+1)
    for i in range(p):
        check_list[i] = a_list[i]
    for i in range(p, N+1):
        check_list[(i-1) % (p-1) + 1] += a_list[i]
    for i in range(p):
        if check_list[i] % p != 0:
            r = 1
    if r == 0:
        res_list.append(p)
        



for p in p_list_large:
    r = 0
    for i in range(N+1):
        if a_list[i] % p != 0:
            r = 1
    if r == 0:
        res_list.append(p)
        
for p in res_list:
    print(p)

Solution (Python):
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

def eratosthenes(n):
    if n < 2:
        return []
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

N = int(input())
A = [int(input()) for i in range(N+1)]
g = abs(A[0])
for a in A:
     g = gcd(g,abs(a))
d = prime_decomposition(g)
ans = [p for p in d]

prime = eratosthenes(N+1)
A.reverse()
for p in prime:
    if A[0]%p != 0:
        continue
    for n in range(1,p):
        s = 0
        for k in range(int((N-n)/(p-1))+1):
            s += A[n+k*(p-1)]
            s %= p
        if s != 0:
            break
    if s == 0:
        ans.append(p)

ans = list(set(ans))
ans.sort()

for p in ans:
    print(p)

Solution (Python):
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

def eratosthenes(n):
    if n < 2:
        return []
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

def ok(p):
    if A[0]%p != 0:
        return False
    B = [A[i]%p for i in range(1,N+1)]
    mod = [0]*(p-1)
    for i in range(N):
        mod[i%(p-1)] += B[i]
        mod[i%(p-1)] %= p
    return sum(mod)==0

N = int(input())
A = [int(input()) for i in range(N+1)][::-1]
g = abs(A[0])
for a in A:
     g = gcd(g,abs(a))
d = prime_decomposition(g)
ans = [p for p in d]

prime = eratosthenes(N+1)

for p in prime:
    if ok(p):
        ans.append(p)

ans = list(set(ans))
ans.sort()

for p in ans:
    print(p)