에라토스테네스의체1 소수 구하기 (자바스크립트) 소수 (Prime number) 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 정수론에서 매우 중요한 주제이며, 특히 현대사회에서 암호학에서 많이 사용하여서 매우 중요해졌다. 출처: 위키백과 소수 판별하기 (JavaScript) 소수를 판별하는 방법은 여러가지가 있다. 그 중 아래의 두가지를 소개한다. 이 판별법은 입력값이 소수인지 아닌지를 판별하는 방법이다. 이를 응용해서 소수의 개수를 구할수도 있다. 반복문 (제곱근으로 최적화 가능) 에라토스테네스의 체 1. 반복문 1) 가장 기본적인 방법으로 반복문을 수행하면서 1이외의 수로 나누어 떨어지지 않는지 확인한다. 이때 시간복잡도는 O(n)이 된다. function isPrime(num) { if(num === 1) return .. 2022. 9. 3. 이전 1 다음