C++ 알고리즘 기초19 -반복문 심화3(무한루프 만들기, 비교연산자 주의할점, 반복문에서 i값 가져오기)-

1. 완전수 판별하기 숫자 n이 주어졌을 때, n이 완전수인지 판단하는 프로그램을 작성해보세요. 완전수란 자기 자신을 제외한 약수의 합이 자신이 되는 수를 나타냅니다. 예를 들어 6의 경우 1 + 2 + 3 = 6 이기 때문에 완전수입니다. n이 1000이하니까 $O(\sqrt{n})$으로 나눠볼 필요는 없을 것 같고 1부터 n-1까지 n을 나눠보면서 약수라면 누적합해준 다음에 반복문을 탈출하고 누적합한 값이 n과 같은지 비교해보면 되겠지 #include using namespace std; int main() { // 여기에 코드를 작성해주세요. int n; cin >> n; int answer = 0; for(int i = 1; i < n; i++){ if(n % i == 0){ answer += i..

• format_list_bulleted C++ 기초
• · 2023. 6. 7.
• textsms

어떤 수를 서로소 쌍의 곱으로 빠르게 분해하는 방법

1. 문제 2436번: 공약수 (acmicpc.net) 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 2. 풀이 최대공약수 G, 최소공배수 L이 주어질때 두 수 x,y는 어떻게 구할까 $$x = Gk_{1}$$ $$y = Gk_{2}$$ 이 때 L은 다음과 같이 구할 수 있다 $$L = Gk_{1}k_{2}$$ 따라서 $k_{1}k_{2}$는 L//G로 일정하다. 그러므로 우리는 L//G를 만드는 두 서로소 $k_{1}$과 $k_{2}$를 찾으면 된다. 여기서 $k_{1}$과 $k_{2}$는 1 이상의 자연..

• format_list_bulleted 정수론
• · 2023. 3. 8.
• textsms

최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법

1. 최대공약수 두 자연수 a,b가 공통으로 가지는 약수중에서 가장 큰 약수를 최대공약수라고 부른다. 중요한 성질중 하나는 최대공약수의 약수는 a,b의 공약수이다. 2. 유클리드 호제법 두 양의 정수 a,b (a>b)에 대하여 a = bq + r ( r은 0이상 b 미만)이라고 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다. 즉, gcd(a,b) = gcd(b,r)이다. 만약 r=0이라하면, a,b의 최대공약수는 b이다. 3. 유클리드 호제법 활용 단 1번만 사용해서는 그 진짜 힘을 알 수 없다. a = bq + r이면 a,b의 최대공약수는 b,r의 최대공약수와 같다 b를 r로 나눠서 b = rq2 + r2라는 식을 얻는다면, 결국 b,r의 최대공약수는 r,r2의 최대공약수와 같다. 여기서 r을..

• format_list_bulleted 정수론
• · 2022. 8. 10.
• textsms