오일러 피함수1 소인수 분해, 약수의 개수, 오일러 피함수 에라토스테네스 :https://suuntree.tistory.com/36?category=805933 소인수분해 자체로는 문제가 많이 나오지않지만 오일러 피함수는 알고있어야 한다. 1. 소인수분해 : O(loglogn) -> while문 수행횟수 log, while문에서 n의 범위를 줄여줌 n이 소수가 아니라면, n은 루트n 이하의 소인수를 갖는다. i==2부터 차례대로 n을 나눌 수 있다면 i로 n을 더이상 나눌 수 없을 때까지 나누면서 진행한다. 과정이 끝나면 n=1 또는 n=소수가 된다. ll n; cin >> n; vector p; for (ll i = 2; i * i 2020. 1. 30. 이전 1 다음
