-
12977. 소수 만들기(Python, Programmers Level 1)Programmers 2022. 9. 5. 01:38
문제 설명
주어진 숫자 중 3개를 더했을 때 소수인 경우의 개수를 구합니다.
코드1
서로 겹치지 않는 인덱스의 숫자 세 개를 더한 수를 만듭니다.
n = len(nums) for i in range(n): for j in range(1 + i, n): for k in range(1 + j, n): num = nums[i] + nums[j] + nums[k] if all(num % m != 0 for m in range(2, int(num ** 0.5) + 1)): answer += 1
2 ~ n ** 0.5 범위의 숫자로 나누어 떨어지는 숫자가 하나도 없는 경우가 소수인 경우입니다.
if all(num % m != 0 for m in range(2, int(num ** 0.5) + 1)): answer += 1
더보기def solution(nums): answer = 0 n = len(nums) for i in range(n): for j in range(1 + i, n): for k in range(1 + j, n): num = nums[i] + nums[j] + nums[k] if all(num % m != 0 for m in range(2, int(num ** 0.5) + 1)): answer += 1 return answer if __name__ == '__main__': result = solution([1, 2, 3, 4]) print(1 == result, result) result = solution([1, 2, 7, 6, 4]) print(4 == result, result)
코드2
문제를 해결하는 데 필요한 소수를 모두 미리 계산합니다.
에라토스테네스의 체를 사용합니다.
is_prime 배열은 이 숫자가 소수인지 아닌지를 판별할 수 있게 할 것입니다.
각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않으므로,
최대 2997(1000 + 999 + 998)까지의 범위를 갖습니다.0 ~ 2997(2998개)를 표현할 수 있는 배열을 만듭니다.
is_prime = [True] * 2998
0과 1은 소수가 아닙니다.
is_prime[0] = is_prime[1] = False
숫자를 나눌 수 있는 수가 있다면, 그 수 혹은 그 수로 나눈 몫은 root 이내의 범위에 존재합니다.
어떤 숫자가 소수라면, 그 수의 배수는 소수가 아닙니다.
어떤 숫자가 소수가 아니라면, 그 수의 배수는 소수가 아님이 이미 확인되어있을 것입니다.
for i in range(2, int(2998 ** 0.5) + 1): if is_prime[i]: for j in range(i * 2, 2998, i): is_prime[j] = False
num 내 세 숫자를 더해 나온 수가 소수인지, is_prime 배열을 통해 확인합니다.
n = len(nums) for i in range(n): for j in range(1 + i, n): for k in range(1 + j, n): if is_prime[nums[i] + nums[j] + nums[k]]: answer += 1
더보기def solution(nums): answer = 0 is_prime = [True] * 2998 is_prime[0] = is_prime[1] = False for i in range(2, int(2998 ** 0.5) + 1): if is_prime[i]: for j in range(i * 2, 2998, i): is_prime[j] = False n = len(nums) for i in range(n): for j in range(1 + i, n): for k in range(1 + j, n): if is_prime[nums[i] + nums[j] + nums[k]]: answer += 1 return answer if __name__ == '__main__': result = solution([1, 2, 3, 4]) print(1 == result, result) result = solution([1, 2, 7, 6, 4]) print(4 == result, result)
'Programmers' 카테고리의 다른 글
42576. 완주하지 못한 선수(Python, Programmers Level 1) (0) 2022.09.06 1845. 폰켓몬(Python, Programmers Level 1) (0) 2022.09.05 70128. 내적(Python, Programmers Level 1) (0) 2022.09.04 76501. 음양 더하기(Python, Programmers Level 1) (0) 2022.09.04 86051. 없는 숫자 더하기(Python, Programmers Level 1) (0) 2022.09.04