목록약수 (1)

마이 플밍 블로그

[알고리즘] 약수 구하기 알고리즘

보통 가장 간단한 모든 약수를 구하는 알고리즘하면 1부터 N까지 반복문을 돌려 N % i == 0 일경우 약수로 하는 알고리즘을 생각할 것이다. 이경우 시간 복잡도는 O(N)이 되는데 O(√N) 으로 줄일 수있다. 방법은 간단하다. N의 약수들 중 √N 이하의 것들을 구하고 그 것들을 N에 나누면 다른 약수들도 구할 수있다. 예를 들어서 111의 약수를 구할 때 √110 이하의 약수들은 1, 2, 5, 10 이고 이 것들을 110에 나누면 11, 22, 55, 110 이 나온다. #include #include #include using namespace std; vector vec; int main() { int n = 110; // sqrt를 안쓰고 i * i를 이용함 for (int i = 1; i..
알고리즘 2022. 4. 29. 06:13
이전 Prev 1 Next 다음