CS & 알고리즘/알고리즘

소수란 1과 자기 자신 만을 약수로 가지는 수기본적인 소수 구하는 방법반복문을 통해 1과 자기 자신을 제외한 숫자로 나누었을때모두 % != 0 나머지가 0이 아니면 소수이다N 의 약수는 무조건 1 ~ $\sqrt{N}$ 안에 존재한다이 방법을 통해 시간복잡도 $O(\sqrt{n})$ 까지 감소 가능구현예시 double sqrt = Math.sqrt(N); for (int i = 2; i 위 코드에서 sqrt 를 for 문 안에 넣으면 반복문 돌때마다 계산하므로 비효율적for (int i = 2; i * i 으로 써도 동일함시간복잡도 : $O(\sqrt{n})$ 에라토스테네스의 체 활용방법특정 범위 내에서 여러 숫자가 소수인지 판별할때 유리한 알고리즘낮은 시간복잡도, 높은 공간복..