SWE(5986)새샘이와_세_소수

작성일 | In

SWE 5986 세샘이와 세 소수

  • 정수론에서 세 소수 문제란 다음과 같다.
  • “5보다 큰 모든 홀수는 정확히 세 소수의 합으로 표현될 수 있다.
  • 5보다 큰 홀수 N을 입력 받아, N = x+y+z로 나타나는 경우의 수를 구하는 프로그램을 작성하라

풀이방법

  • N 이전의 소수를 미리 구한다. -> 에라토스테네스의체 사용
  • N 이전의 소수를 구한 것 중 3개를 뽑아, 그 값이 N이 되는 경우의 수를 구한다.

오답

  • 시간 초과
  • 1000개 중 137개가 맞았다고 한다.
from itertools import combinations_with_replacement as cwr

TC = int(input())

for tc in range(1, TC+1):
    N = int(input())
    # N 이전의 소수 미리 구하기
    prime = set(range(2, N+1))
    for i in range(2, N+1):
        if i in prime:
            prime -= set(range(i*2, N, i))
    result = 0
    for i in cwr(prime, 3):
        if sum(i) == N:
            result += 1
    print(f"#{tc} {result}")
  • 미리 중복 조합을 구해 놓은 뒤, sum으로 푸는 방법은 시간이 오래걸린다.

어떻게 해야할까?

  • 다른 사람 풀이를 참고했다.

    미리 1000까지 소수를 구해놓자.

제출 코드

prime = []
# N 이전의 소수 미리 구하기
prime = set(range(2, 1000))
for i in range(2, int(1000//2)+1):
    if i in prime:
        prime -= set(range(i*2, 1000, i))
prime = list(prime)
TC = int(input())

for tc in range(1, TC+1):
    N = int(input())
    # print(prime)
    result = 0
    for i in range(len(prime)):
        for j in range(i, len(prime)):
            if N - (prime[i] + prime[j]) in prime[j:]:
                result += 1
    print(f"#{tc} {result}")

코드 풀이


demical_num = [] # 소수를 미리 구해놓고,인덱스로 계산하기 위해서 리스트로 선언, 전역변수 선언

def check_num(num): # 소수인지 판별하는 함수
    for i in range(2,int(num/2) + 1):
        if num % i == 0 :
            return False
    return True


for i in range(2,1000): # 소수인지 혹인해서 demical_num에 추가
    if check_num(i):
        demical_num.append(i)

for rounds in range(int(input())): # 이런 식으로 input을 range()안에 적을 수도 있다
    goal = int(input())
    count = 0
    for i in range(len(demical_num)):
        for j in range(i, len(demical_num)): # i가 한번 나왔다면, i부터 체크해줌으로써, 그 다음 소수를 체크해주는 방식
            if goal - (demical_num[i] + demical_num[j]) in demical_num[j:]:
            # 순서대로 정렬되어 있기 때문에, 오른쪽에 있는 리스트의 값이 안
            에 들어있는 지만 확인하면 된다.
                count += 1
    print(f'#{rounds + 1} {count}')

참고자료 [SWexperacademy]https://swexpertacademy.com [중복여부에따른permutations,combinations]https://ghwlchlaks.github.io/permutation-combination-python

0%