Hackerrank - Running Time and Complexity

https://www.hackerrank.com/challenges/30-running-time-and-complexity/editorial

Day 25: Running Time and Complexity | HackerRank

이번에 푼 문제는 "소수(Prime Number) 여부 판별하기"입니다.

소수란, "1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수"를 의미합니다.

예를 들어, 2, 3, 5, 7, 11, 13....과 같은 숫자들이 있습니다.

 

특정 숫자를 Input으로 받을 때, 해당 숫자가 소수인지 아닌지를 판별하여,

맞다면 "Prime", 아니라면 "Not Prime"을 출력하면 됩니다.

 

* 소수 판별하기 : 

  저는 약간 다른 방향으로 접근해서 풀긴 했지만, 결국 같은 내용이므로 최적 알고리즘에 대해 설명하겠습니다.

시간과 공간을 고려하지 않는다면, n을 1부터 n-1까지의 수로 모두 나눠본 뒤 소수인지 아닌지를 판별할 수도 있습니다. 하지만 항상 시간과 메모리는 제한되어있기 때문에, 최적의 알고리즘을 찾아야 합니다.

  특정 숫자 n이 주어졌을 때, n은 소수가 아니라면 양의 정수 a,b의 곱으로 나타낼 수 있습니다. 이 때, a와 b는 동시에 루트 n보다 커질 수 없습니다. 두 수 모두 루트 n보다 클 경우, a*b > n 이 될 것이기 때문이죠.

이 조건을 활용하면,

 

i) a ≤ 루트 n

이라는 조건을 찾을 수 있습니다. 우리는 특정 수 n이 주어졌을 때, [1, 루트n] 범위 내의 숫자에 대해서 n의 인수인지 확인해보면 최종적으로 n의 소수 여부를 판별할 수 있습니다.

(이 때, a의 counterpart로 지정된 b에 대해서는 고려하지 않아도 됩니다. 아래 표와 같이, a*b나 b*a나 같으니까요.)

 

 

1. 변수

  1) bound : 주어진 숫자 a가 나눠지는지 확인해볼 숫자들의 범위(루트 n으로 지정하면 됩니다. 저는 조금 다른 방법으로 접근했으나 결국 같은 방법이었습니다.)

  2) count : 확인 횟수

2. 방법

  1) 루트 a보다 작은 숫자에 대해서 a가 나눠지는지 테스트해봅니다.

  * 이 때, 2는 별도로 걸러줘야 합니다. 2는 소수이기 때문입니다.

  ** 이 때, 2에 대해서 나눠지는지 여부를 먼저 확인하면 테스트해볼 범위의 수를 반이나 줄일 수 있습니다. 2로 나눠지는지 먼저 확인하고, 나눠지지 않는다면 홀수에 대해서만 테스트를 진행합니다.

 

이상 끝-!