목록Math (1)
Pko
소수 인지 판단
소수 약수가 1과 자기 자신 밖에 없는, 1보다 큰 자연수. 한편 1보다 큰 자연수 중 소수가 아닌 것은 합성수(composite number)라고 한다. 소수의 개수는 무한하며, 이는 유클리드의 정리에 의해 증명되었다. N이 소수가 되려면, 2보다 크거나 같고 N-1보다 작거나 같은 자연수로 나누어 떨어지면 그 값은 소수가 아니기 때문에 이 방법을 다음과 같은 코드작성 할수 있다. funtion isPrime(num) { if( num < 2 ) return false for (let i = 2; i < num; ++i) { if (num % i == 0) return false; } return true; } 그러나 이런 식으로 구현할시 복잡도는 O(n)이 된다 이 복잡도를 줄이기 위해 방법을 고민하..
Math
2021. 6. 17. 17:05