Algorithm_Java
[알고리즘] 백준 1929 소수 구하기 - 에라토스테네스의 체
문제 본문 소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수입니다. 대표적으로 2, 3, 5, 7.. 등등이 있습니다. 단순 소수 찾기 - O(n^2) public static boolean isPrime(int num) { if (num == 1) return false; for (int n = 2; n < num; n++) { if (num % n == 0 ) { return false; } } return true; } 가장 간단하게 소수를 구하는 방법은 1을 제외하고 자신보다 작은 자연수로 나누어 나머지가 0이 나오는 지 확인하는 것입니다. 하지만 위 방법은 O(n^2)의 시간 복잡도를 가져서 num의 값이 크다면 시간초과를 발생합니다. 제곱근을 활용하여 소수 찾기 -..
