목록2024/10/11 (1)
나만의 작은 도서관
[알고리즘] 소수 판별법과 에라토스테네스의 체
소수 판별법소수는 양의 약수를 2개만 가지는 자연수, 즉 1과 자기자신으로만 나누어 떨어지는 자연수를 의미한다(1 제외). 임의의 수 N이 소수인지 판별하기 위해선 2~N-1까지의 수들로 N이 나누어 떨어지지 않는 지 확인하면 된다. 코드로 구현하면 다음과 같다.// 시간복잡도 O(N)bool isPrime(int num){ for(int i = 2; i 최적화를 할 수는 없을까?위 코드는 최적화가 가능하다. 2 이상의 자연수 N에 대해서 N의 약수는 짝이 반드시 존재하고, 짝이 되는 약수 중 작은 쪽에 속하는 약수는 √ N을 초과할 수 없기 때문에 num까지가 아닌 √ N이하의 자연수까지만 루프를 돌면 된다. 따라서 코드에 적용하면 다음과 같다.// 시간복잡도 O(√N)bool isPrime(i..
C++/알고리즘
2024. 10. 11. 19:45