쉽게 쉽게

▤ 목차1. 소수 구하기1. 방법1 (N까지 나누기)N 보다 작은 자연수들로 나눈 후 소수인지 아닌지 판별하는 알고리즘이다.  시간복잡도: O(N²)public boolean isPrime(int n) { if (n 2. 방법2 (N의 제곱근보다 작은 수까지 나누기)첫 번째 방법에서 좀 더 발전된 방법으로 소수를 구할 때 N의 제곱근(√) 까지만 나눈다.소수인지 판별할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나기 때문에 제곱근까지만 판별하면 된다. 만약 n=36일 때1×36=362×18=363×12=364×9=366×6=36 (제곱근에서 대칭의 끝) 즉, 약수는 작은 수와 큰 수로 짝을 이루고 있으며, 그 짝 중 하나는 항상 √n​보다 작거나 같고, 다른 하나는 ..