[COS PRO 1급] 3차 문제6) 소수의 합으로 표현하기

아현·2023년 9월 13일
0

Algorithm

목록 보기
391/400

연습문제


어떤 수를 서로 다른 소수 3개의 합으로 표현하는 방법의 수를 구하려 합니다.
예를 들어 33은 총 4가지 방법으로 표현할 수 있습니다.

3+7+23
3+11+19
3+13+17
5+11+17

자연수 n이 매개변수로 주어질 때, n을 서로 다른 소수 3개의 합으로 표현하는 방법의 수를 return 하도록 solution 함수를 작성하려 합니다. 빈칸을 채워 전체 코드를 완성해주세요.
※ 1,000 이하인 소수는 168개 있습니다.

□ 매개변수 설명

n이 solution 함수의 매개변수로 주어집니다.
n은 1,000 이하인 자연수입니다.

□ return 값 설명

n을 서로 다른 소수 3개의 합으로 표현하는 방법의 수를 return 해주세요.
만약, n을 서로 다른 소수 3개의 합으로 표현할 수 없다면 0을 return 해주세요.





# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
def solution(n):
	answer = 0
	primes = [2]
	for i in range (3, n + 1, 2) :
		is_prime = True
		for j in range(2, i) :
			if i % j == 0 :
				is_prime = False
				break
		if is_prime:
			primes.append(i)

	prime_len = len(primes)
	for i in range(0, prime_len - 2) :
		for j in range(i + 1, prime_len - 1) :
			for k in range(j + 1, prime_len) :
				if primes[i] + primes[j] + primes[k] == n :
					answer += 1
	return answer

profile
For the sake of someone who studies computer science

0개의 댓글