짹뚜 스튜디오

소수란 1 보다 큰 정수 중 약수로 1과 자기 자신만을 가지는 정수이다. 그러므로 임의의 정수가 소수인지를 판별하기 위해서는 2부터 n-1까지의 정수로 나누기를 해서 나머지가 0이 나오는지 안 나오는지로 확인할 수 있다. function isPrime(n){ for(let i = 2; i < n; i++){ if(n % 2 === 0){ return false; } } return true; } 하지만 위 방식으로 하면 시간복잡도가 O(n)이 나온다. 다른 접근 방식으로는 약수의 중심을 구하는 공식을 이용하면 된다. 어느 한 정수의 약수들 중에서 두 개의 약수를 곱해서 해당 정수가 나오는 값끼리 한 쌍으로 묶었을 때 하나의 약수는 무조건 해당 정수의 제곱근보다 작은 수이다. 예를 들어 정수 50의 약수는..