<div id="readability-page-1" class="page">
                
                
                


<div id="wrap">
	
	<hr>
	<section>
		
		<article id="content">
			

			

			

			

			<div>
				

				            
                
	
	
		<div>
			<p>운동하는 개발자/알고리즘, 코딩테스트</p>
			
			<p>
				<span>2023. 12. 25. 17:23</span>
				
			</p>
		</div>
		<div><hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
<h3 data-ke-size="size23"><br>🅰️문제주소 :<span> <a href="https://www.acmicpc.net/problem/11689" target="_blank" rel="noopener&nbsp;noreferrer">https://www.acmicpc.net/problem/11689</a></span></h3>

<h3 data-ke-size="size23"><br>🚩문제&nbsp;</h3>
<figure data-ke-mobilestyle="widthOrigin" data-origin-width="820" data-origin-height="120"><span data-url="https://blog.kakaocdn.net/dn/bZkydC/btsCycctHJi/ge7N4qtebkG6JJ9Hr7paEK/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/bZkydC/btsCycctHJi/ge7N4qtebkG6JJ9Hr7paEK/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="820" data-origin-height="120"></span></figure>



<h3 data-ke-size="size23">🪡풀이&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 주어진 수에서 그 수보다 작은 자연수 중 최대공약수가 1이 되는 수(서로소)의 개수를 구하는 것으로 오일러의 피 함수를 구현할 줄 아는지 묻는 문제<br>&nbsp;- 소수를 구하는 에라토스테네스의 체와 비슷하게 구현가능한데 배수를 0으로 지우는 부분 대신 P[i] = P[i] -[Pi]/K 로 변경해 주면 된다<br>&nbsp;- 해당문제는 한번의 입력만 주어지기에 따로 배열에 저장할 필요 없이 매번 새로 구하게 하면 된다</p>


<h3 data-ke-size="size23">☕코드는 아래 숨김</h3>
<div data-text-less="닫기" data-text-more="더보기" data-ke-type="moreLess"><p><a>더보기</a></p><div>
<pre id="code_1701091944942" data-ke-language="cpp" data-ke-type="codeblock"><code>#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;math.h&gt;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    long long n;

    std::cin &gt;&gt; n;

    long long result = n;

    for (int i = 2; i &lt;= std::sqrt(n); ++i) { //제곱근까지만 진행함
        if (n % i == 0) { //i가 소인수인지 확인함 
            result = result - result / i; //결과값 개수를 업데이트 함
            while (n % i == 0) { //소인수 i를 바로바로 지움 중복삭제를 방지
                n /= i;
            }
        }
    }
    if (n &gt; 1) { //제곱근까지 진행했기에 1개의 소인수가 누락될 수 있음 
        result = result - result / n;
    }


    std::cout &lt;&lt; result;
    return 0;
}</code></pre>
</div>
</div>

<h3 data-ke-size="size23">💡알게 된 것&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 오일러의 피 함수<br>&nbsp;- 기초 수학 용어들 remind...<br>&nbsp; &nbsp; &nbsp;1) GCD : 최대공약수<br>&nbsp; &nbsp; &nbsp;2) 서로소 : 두 수의 최대공약수가 1, 최소공배수는 두수의 곱&nbsp;&nbsp;<br>&nbsp; &nbsp; &nbsp;3) 소인수 : 자연수를 나누어 떨어지는 수 중 소수인 것 (10의 경우 1 2 5 10 중 2, 5에 해당)</p>
<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
</div>
		

		
			<div>
				<h2><strong>'운동하는 개발자/알고리즘, 코딩테스트'</strong> Related Articles</h2>
				
			</div>
		

		



	

                
            
			</div>

			

			

			

		</article>
	</section>
	<hr>
	
	
</div>







                




        
        











  


        

                
                







                
                


                

</div>

운동하는 개발자

️문제주소 : https://www.acmicpc.net/problem/11689
 
 문제 
 
 
 풀이 
 - 주어진 수에서 그 수보다 작은 자연수 중 최대공약수가 1이 되는 수(서로소)의 개수를 구하는 것으로 오일러의 피 함수를 구현할 줄 아는지 묻는 문제
 - 소수를 구하는 에라토스테네스의 체와 비슷하게 구현가능한데 배수를 0으로 지우는 부분 대신 P[i] = P[i] -[Pi]/K 로 변경해 주면 된다
 - 해당문제는 한번의 입력만 주어지기에 따로 배열에 저장할 필요 없이 매번 새로 구하게 하면 된다
 
 
☕코드는 아래 숨김
더보기
#include <iostream>
#include <vector>
#include <math.h>
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    long long n;
    std::cin >> n;
    long long result = n;
    for (int i = 2; i <= std::sqrt(n); ++i) { //제곱근까지만 진행함
        if (n % i == 0) { //i가 소인수인지 확인함 
            result = result - result / i; //결과값 개수를 업데이트 함
            while (n % i == 0) { //소인수 i를 바로바로 지움 중복삭제를 방지
                n /= i;
            }
        }
    }
    if (n > 1) { //제곱근까지 진행했기에 1개의 소인수가 누락될 수 있음 
        result = result - result / n;
    }
    std::cout << result;
    return 0;
}
 
 알게 된 것 
 - 오일러의 피 함수
 - 기초 수학 용어들 remind...
     1) GCD : 최대공약수
     2) 서로소 : 두 수의 최대공약수가 1, 최소공배수는 두수의 곱  
     3) 소인수 : 자연수를 나누어 떨어지는 수 중 소수인 것 (10의 경우 1 2 5 10 중 2, 5에 해당)

Beakjoon] GCD(n, k) = 1 aka.오일러의 피 (백준 11689 코테) - 정수론 (C++)

댓글