728x90
문제 설명
[과제] 본 문제는 에라토스테스트의 체 알고리즘을 이용해서 풀어주세요. 에라토스테스트의 체를 모른다면, 앞선 collab 자료를 참고해주세요!
어떤 수를 서로 다른 소수 3개의 합으로 표현하는 경우의 수를 구하려 합니다. 예를 들어 33은 총 4가지 방법으로 표현할 수 있습니다.
- 3+7+23
- 3+11+19
- 3+13+17
- 5+11+17
자연수 n이 매개변수로 주어질 때, n을 서로 다른 소수 3개의 합으로 표현하는 경우의 수를 return 하는 solution 함수를 작성해주세요.
제한 조건
- n은 1,000 이하인 자연수입니다.
입출력 예
| n | return |
| 33 | 4 |
| 9 | 0 |
입출력 예 설명
예시 #1
문제에 나온 예와 같습니다.
예시 #2
9는 서로 다른 세 소수의 합으로 나타낼 수 없습니다.
#코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
from itertools import combinations
def solution(n):
# 1. 에라토스테스트의 체 구현
prime_list = list( ) # 소수 리스트
num_list = [True] * (n + 1)
num_list[0] = False
num_list[1] = False
for i in range(2, (n + 1)):
if num_list[i] == True:
prime_list.append(i)
for j in range((i * 2), (n + 1), i):
num_list[j] = False
# 2. 답을 구한다.
# 질문 : o(n^3) 이므로 시간초과가 나는 것을 알지만 combination 라이브러리 없이 개선시킬 수 있을까?
'''
cnt_set = set()
for i in range((len(prime_list) - 2)):
for j in range((i + 1), (len(prime_list) - 1)):
for k in range((i + 2), (len(prime_list))):
if prime_list[i] != prime_list[j] and prime_list[j] != prime_list[k] and prime_list[i] != prime_list[k]:
my_val = prime_list[i] + prime_list[j] + prime_list[k]
if my_val == n:
tmp_list = [prime_list[i], prime_list[j], prime_list[k]]
tmp_list.sort()
cnt_set.add(tuple(tmp_list))
'''
return [sum(c) for c in combinations(prime_list, 3)].count(n)
|
cs |
# 코드2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
def solution(n):
# 1. 에라토스테스트의 체 구현
prime_list = list( ) # 소수 리스트
num_list = [True] * (n + 1)
num_list[0] = False
num_list[1] = False
for i in range(2, (n + 1)):
if num_list[i] == True:
prime_list.append(i)
for j in range((i * 2), (n + 1), i):
num_list[j] = False
# 2. 답을 구한다.
answer = 0
for i in range((len(prime_list))):
for j in range(i + 1, len(prime_list)):
for k in range(j + 1, len(prime_list)):
my_val = prime_list[i] + prime_list[j] + prime_list[k]
if my_val == n:
answer += 1
return answer
|
cs |
반응형