Jinho Tech

단순한 수학 문제이다. N이 4의 배수이면 짝수, N이 2의 배수이면 홀수, N이 홀수이면 짝수, 홀수 둘다 가능하다.

N = int(input())
if N%4 == 0:
    print("Even")
elif N%2 == 0:
    print("Odd")
else:
    print("Either")

기본적인 소수 판정(에라토스테네스의 체) 문제이다.

def prime(n):
    li = [1]*(n+1)
    for i in range(2, int(n**0.5)+1):
        if li[i]:
            for j in range(i+i, n+1, i):
                li[j] = 0
    p = [i for i in range(2, n+1) if li[i]]
    return p

while 1:
    s = input()
    if s == '0':
        break
    p = prime(100000)
    res = 2
    for n in p:
        if str(n) in s:
            res = n
    print(res)

기본적인 소수 판정(에라토스테네스의 체) 문제이다.

INF = 10**7
li = [1]*INF
for i in range(2, int(INF**0.5)+1):
    if li[i]:
        for j in range(i+i, INF, i):
            li[j] = 0
prime = [i for i in range(2, INF) if li[i]]
K = int(input())
print(prime[K-1])    

간단한 소수 판정(에라토스테네스의 체) 문제이다. 그냥 무식하게 풀었다.

def f(K, prime):
    for i in prime:
        for j in prime:
            for k in prime:
                if i+j+k == K:
                    print(i, j, k)
                    return ;
    print(0)

li = [1]*1001
for i in range(2, int(1000**0.5)+1):
    if li[i]:
        for j in range(i+i, 1001, i):
            li[j] = 0
prime = [i for i in range(2, 1001) if li[i]]

for _ in range(int(input())):
    K = int(input())
    f(K, prime)

간단한 소수 판정(에라토스테네스의 체) 문제이다.

A, B, D = map(int, input().split())
li = [1]*(B+1)
for i in range(2, int(B**0.5)+1):
    if li[i]:
        for j in range(i+i, B+1, i):
            li[j] = 0
prime = [i for i in range(A, B+1) if li[i]]
cnt = 0
for n in prime:
    if str(D) in str(n):
        cnt += 1
print(cnt)

난이도가 있는(시간 초과) 수학 문제이다. 0부터 시작해서 제곱 값들을 확인하면

무조건 시간 초과가 나오기 때문에 a보다 크거나 같은 제곱수들만 확인해야 한다. 

a, b = map(int, input().split())
li = [1]*(b-a+1)
for i in range(2, int(b**0.5)+1):
    t = i**2
    for j in range(a//t*t, b+1, t):
        if j-a >= 0 and li[j-a]:
            li[j-a] = 0
print(li.count(1))

에라토스테네스의 체를 사용해야 하는 소수 문제이다. 9020번 골드바흐의 추측 문제와 비슷한 문제인데 

시간 초과 관련해서 더 훨씬 힘든 것 같다.

핵심은 1000000 까지의 소수를 미리 다 찾아놓고 while문을 돌리는 것이다. 안 그러면 시간 초과가 나온다. 

import sys

li = [1]*(1000001)
for i in range(2, int(1000001**0.5) + 1):
    if li[i] == 1:
        for j in range(i+i, 1000001, i):
            li[j] = 0

while 1:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    a = b = 0
    for i in range(2, n//2+1):
        if li[i] == 1 and li[n-i] == 1:
            a, b = i, n-i
            break
    if a+b:
        print(f"{n} = {a} + {b}")
    else:
        print("Goldbach's conjecture is wrong.")

단순 수학 문제이다.

a, m = map(int, input().split())
for i in range(1, 10001):
    if a*i % m == 1:
        print(i)
        break

단순 수학 문제이다. 최대공약수를 구해주는 재귀 함수는 기억해두는 것이 좋을 것 같다. 

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

n1, d1 = map(int, input().split())
n2, d2 = map(int, input().split())
n = n1*d2 + d1*n2
d = d1*d2
g = gcd(max(n,d), min(n,d))
print(n//g, d//g)

생각보다 쉬운 문제이다. 30의 배수이려면 일단 맨 마지막 자리의 숫자가 0이어야 한다. 

그리고 3의 배수인지 확인하는 방식과 동일하게 30의 배수는 각 자리 숫자들의 합이 3의 배수이어야 한다.

이 점들과 정렬을 사용하면 문제를 정말 쉽게 풀 수 있다. 

숫자 안에 0이 안 들어있으면 어차피 30의 배수가 안되고, 0이 들어있어도 각 자리 숫자들의 합이 3의 배수가 아니면 어차피 30의 배수가 아니기에, 그냥 입력을 내림차순 정렬한 수가 30의 배수이면 출력, 아니면 -1을 출력해주면 된다. 

EX) n = 102 -> 210 -> 210%30 == 0 -> Ok!

EX) n = 2931 -> 9321 -> 9321%30 != 0 -> No!

s = sorted(input(), reverse=True)
n = int(''.join(s))
print(n if n % 30 == 0 else -1)

정확하게 이해한 건지는 모르겠지만

2부터 1000까지의 정수를 나눴을 때 나머지가 모두 같은 수를 찾으라는 것 같다. 

-1은 2부터 1000까지의 정수 중 어떤 수로 나누든 나머지가 -1이다!

print(-1)

소수 관련 문제이다. 에라토스테네스의 체를 사용하면 쉽다.

n1, a = input().split()
n2 = int(a+n1)
n1 = int(n1)

li = [1]*(n2+1)
for i in range(2, int(n2**0.5)+1):
    if li[i] == 1:
        for j in range(i+i, n2+1, i):
            li[j] = 0
prime = [i for i in range(2, n2+1) if li[i] == 1]
print("Yes" if n1 in prime and n2 in prime else "No")

단순 수학 문제이다.

n이 홀수 -> 합이 홀수, 짝수 둘 다 가능함
EX) n = 3
1 + 2 + 3 = 6, 
2 + 3 + 4 = 9

n이 짝수 -> 경우가 두 가지로 나뉨
n//2%2 = 1 -> 합이 홀수임
EX) n = 6
1 + 2 + 3 + 4 + 5 + 6 = (6+1)*3 = 7*3 = 21
2 + 3 + 4 + 5 + 6 + 7 = (7+2)*3 = 9*3 = 27

n//2%2 = 0 -> 합이 짝수임
EX) n = 4
1 + 2 + 3 + 4 = (4+1)*2 = 5*2 = 10
2 + 3 + 4 + 5 = (5+2)*2 = 7*2 = 14

n = int(input())
if n%2:
    res = 0
elif n//2%2 == 0:
    res = 2
else:
    res = 1
print(res)

에라토스네테스의 체를 사용해야 하는 소수 문제이다. 첫번째 코드가 두 번째 코드가 2배 정도 빠르게 나오는데 왜 그런지 모르겠다... 두 번째 코드는 PyPy3로 제출하면 통과는 된다.

for _ in range(int(input())):
    n = int(input())
    li = [1]*(n+1)
    for i in range(2, int((n+1)**0.5) + 1):
        if li[i] == 1:
            for j in range(i+i, n+1, i):
                li[j] = 0
    ans_li = []
    for i in range(2, n//2+1):
        if li[i] == 1 and li[n-i] == 1:
            ans_li.append([i, abs(i-(n-i))])
    ans_li = sorted(ans_li, key=lambda x : x[1])
    print(ans_li[0][0], n - ans_li[0][0])

for _ in range(int(input())):
    n = int(input())
    li = [1]*(n+1)
    for i in range(2, int((n+1)**0.5) + 1):
        if li[i] == 1:
            for j in range(i+i, n+1, i):
                li[j] = 0
    prime = [i for i in range(2, n+1) if li[i]]
    ans_li = []
    for p in prime:
        if n-p in prime:
            ans_li.append([p, abs(p-(n-p))])
    ans_li = sorted(ans_li, key=lambda x : x[1])
    print(ans_li[0][0], n-ans_li[0][0])