Jinho Tech

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

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)

백트래킹 & 소수 판정(에라토스테네스의 체) 문제이다. 꽤 좋은 퀄리티의 문제인 것 같다.

def dfs(depth):
    if depth == M:
        s.add(sum(li))
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        for j in range(i+1, N):
            check[j] = 0

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

N, M = map(int, input().split())
nums = list(map(int, input().split()))
s = set()
li = []
check = [0]*N
dfs(0)
p = prime(1000*M)
ok = 0
if s:
    for n in sorted(s):
        if n in p:
            ok = 1
            print(n, end=' ')
if ok == 0:
    print(-1)

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

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

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

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

그 유명한 에라토스테네스의 체 문제이다. 

에라토스네테스의 체를 사용해 소수 리스트를 만들 때 K(입력) 번째 지우는 수를 구해야 하는 문제이다. 

소수 리스트를 생성하는 과정에서 변수(cnt) 하나만 추가해주면 된다.

N, K = map(int, input().split())  
cnt = 0  
nums = [True] * (N+1)  
for i in range(2, N+2):  
    for j in range(i, N+1, i):  
        if nums[j] == True:  
            nums[j] = False  
            cnt = cnt + 1  
            if cnt == K:  
                print(j)  
                break

에라토스네테스의 체를 사용해야 하는 소수 문제이다. 첫번째 코드가 두 번째 코드가 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])