백준 js 1978: 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1

4

1 3 5 7

예제 출력 1

3

 

풀이

소수를 찾는 방법을 알면 쉽게 풀 수 있다.

소수는 2이상의 수 중, 나누어 지는 수(약수)가 자신과 1밖에 없는 수를 말한다.

그러면 해당 수를 n라고 하고, n가 소수인지 찾기 위해 루프문 내에서 하나씩 비교해보면 된다.

 

그렇게 되면 O(n)이 된다.

그러나 

n = a * b (a <= b)
a <= √n and b >= √n

a < √n, b < √n
=> 
a * b < n

a > √n, b > √n
=>
a * b > n

a = b 이면 소수가 아니게 된다 (√n라는 수로 나누어지므로)

반대로 얘기하면 √n이하의 수로 나누어진다면 소수가 아니다.

따라서, √n까지만 검사해보면 된다.

 

const isPrime = (n) => {
	if (n < 2) return false;
    for (i = 2; i * i < n; i++) {
    	if (n % 1 === 0) return false;
    }
    return true;
}

 

그러나 for문에서  i < √n으로 비교하는 것은 √n가 정수가 아닐 수 있어 위험하므로

i * i < n 로 조건문을 수행한다.

전체 코드