소수 구하기 : isPrime, prime number, sqrt

1. 문제

 

정수 n을 인자로 받아와서 그것이 소수인지 판별하는 함수를 만든다.

 

 

 

소수의 특성

소수는 1과 자기 자신으로만 나누어지는 수이다.

1은 소수가 아니다.

---

2. 풀이

1. 정수 n을 1을 제외한 모든 자연수에 대하여 나눠가며 나누어 떨어지는 수가 있는지 판별한다.

2. 짝수와 제곱근을 이용해 자료의 크기를 줄인다.

 

상세 설명

정수 n을 자연수를 1씩 증가시켜가며 하나씩 나눠볼텐데, 굳이 n까지 모든 수를 통해 나누어볼 필요가 없다.

이것은 2가 소수이고 짝수는 모두 2로 나누어 떨어지기 때문에 짝수를 제외시킬 수 있고,

모든 수는 제곱근의 제곱으로 나타낼 수 있으므로 굳이 제곱근 이상의 수로 나누어볼 필요가 없기 때문이다.

 

예를 들어서 16의 경우 sqrt(16) = 4가 된다. 즉 16 = sqrt(16) * sqrt(16)이다. 이 수는 기하학적 중간!?(마음대로 지어낸 말)이 된다.

1부터 생각해보면 

 

n = a * b

16 = 1 * 16

16 = 2 * 8

16 = 3 * (어떤 복잡한 수)

16 = 4 * 4

16 = 5 * (어떤 복잡한 수이나, 4보다는 작은수)

...

16 = 8 * 2

...

16 = 16 * 1 이 된다.

 

(어떤 복잡한 수이나, 4보다는 작은수) 는 당연히, 4 * 4에 비해서 a=4가 5가 되었으니, b=4는 4보다 작은 값이 되어야 16을 초과하지 않을 것임을 알 수 있다. 즉 어짜피 a에서 4보다 작은 자연수까지 다 검토했으므로(소수인지 아닌지 알기 위해 나누어봤으므로), b에서 나올 4보다 작은 수를 다시 검토해야할 필요가 없다.

 

즉 17이 소수인지 검토하려면, sqrt(17) = 4.xxx 이므로 1~4까지의 숫자로 17을 나눠보기만 하면 되는 것이다.

 

코드

Math.sqrt를 이용한다!