코딩테스트 연습 - 소수 만들기
주어진 숫자 중 서로 다른 3개를 더해 소수가 되는 경우의 수를 구하라.
서로 다른 3개가 될 수 있는 모든 경우의 수를 구한다. 각각의 경우의 수의 숫자 3개를 더한 값을 가지고 소수를 판별한다. 소수 판별에는 여러가지 방법이 있지만 제곱근의 약수까지만 찾는 방법을 택해 문제를 풀었다.
import math
from itertools import combinations
def solution(nums):
answer = 0
numbers = list(combinations(nums, 3))
for i in numbers:
target = sum(i)
for j in range(2, int(math.sqrt(target)) + 1):
if target % j == 0:
break
elif j == int(math.sqrt(target)):
answer += 1
return answer
import math
def is_prime_number(x):
for i in range(2, int(math.sqrt(x))+1):
if x % i == 0:
return False
return True
찾는 수까지 True로 채운 리스트를 만든다. 2를 제외한 2의 배수, 3을 제외한 3의 배수와 같이 sqrt(n)의 배수는 모두 False로 만든다. 2~n까지의 숫자들 중 True인 숫자들이 소수다.
이는 범위에 대한 소수 판별에 유리하다. 시간복잡도 : O(Nlog(logN))
def is_prime_number(n):
# 2부터 n까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n+1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
# 에라토스테네스의 체
for i in range(2, int(math.sqrt(n)) + 1): #2부터 n의 제곱근까지의 모든 수를 확인하며
if array[i] == True: # i가 소수인 경우 i를 제외한 i의 모든 배수를 지우기
j = 2
while i * j <= n:
array[i * j] = False
j += 1
return [ i for i in range(2, n+1) if array[i] ]