SW Expert 아카데미 // 5986

SW Expert 아카데미 5986번 "새샘이와 세 소수" 문제입니다.

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False

TC = int(input())
for tc in range(1, TC+1):
  N = int(input())
  cnt = 0
  for e in primes:
    for j in primes:
      if e <= j <= N-e-j and N-e-j in primes:
        cnt += 1
  print("#%d %d"%(tc, cnt))

입력한 숫자들을 세 소수의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제다.

 

모든 경우마다 1~1000사이의 소수들을 필요로 하므로 반복문 밖에서 에라스토테네스의 체를 활용한 코드를 작성해서 1000이하의 소수들의 리스트를 만들었다.

 

그 후에 이중 for 문을 통해서 소수 두 개를 뺀 수가 소수 리스트에 있는지 확인하고 있다면 조합이 완성되기 때문에 카운트 +1을 해준다.

 

중복이 발생하지 않는지에 대해서 물어본다면 중복은 발생하지 않는다.

 

이중 for문 바로 아래에 대소 비교도 조건에 있기 때문에 그 과정에서 중복을 자연스럽게 걸러진다.