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


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

			

			

			

			<div>
				

				            
                
	
	
		<div>
			<p>운동하는 개발자/알고리즘, 코딩테스트</p>
			
			<p>
				<span>2023. 12. 16. 22:24</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/1929" target="_blank" rel="noopener&nbsp;noreferrer">https://www.acmicpc.net/problem/1929</a></span></h3>
<figure id="og_1702732731078" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="1929번: 소수 구하기" data-og-description="첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)&nbsp;M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다." data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/1929" data-og-url="https://www.acmicpc.net/problem/1929" data-og-image="https://scrap.kakaocdn.net/dn/b2gFta/hyUPzrB1Is/dKiudGzTDfeA4YqPB3K0y1/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"><a href="https://www.acmicpc.net/problem/1929" target="_blank" rel="noopener" data-source-url="https://www.acmicpc.net/problem/1929">

<div>
<p data-ke-size="size16">1929번: 소수 구하기</p>
<p data-ke-size="size16">첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)&nbsp;M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.</p>
<p data-ke-size="size16">www.acmicpc.net</p>
</div>
</a><img src="https://scrap.kakaocdn.net/dn/b2gFta/hyUPzrB1Is/dKiudGzTDfeA4YqPB3K0y1/img.png?width=2834&amp;height=1480&amp;face=0_0_2834_1480"></figure>

<h3 data-ke-size="size23"><br>🚩문제&nbsp;</h3>
<figure data-ke-mobilestyle="widthOrigin" data-origin-width="493" data-origin-height="126"><span data-url="https://blog.kakaocdn.net/dn/kU8hV/btsB3szP95J/CY3DqBOQzMURHTsmVXZ8f1/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/kU8hV/btsB3szP95J/CY3DqBOQzMURHTsmVXZ8f1/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="493" data-origin-height="126"></span></figure>



<h3 data-ke-size="size23">🪡풀이&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 최대 범위가 1,000,000으로 주어졌으므로 에라토스테네스의 체를 사용해야 한다. <br>O(Nlog(logN)) 의 시간복잡도를 가진다<br>&nbsp;- 연산하기 쉽게 0에서 N까지 모두 벡터에 넣은 뒤 에라토스테네스의 체를 돌리며 소수가 아닌 수는 0으로 변경시킨다.<br>&nbsp;- M에서 N사이의 0이 아닌 값을 출력한다.</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);

    int M, N;

    std::cin &gt;&gt; M &gt;&gt; N;

    std::vector&lt;int&gt; nums(N+1, 0);

    for (int i = 0; i &lt;= N; ++i) {
        nums[i] = i;
    }

    if (nums[1] == 1) {
       nums[1] = 0;
    }

    for (int i = 2; i &lt;= std::sqrt(N); ++i) {
        if (nums[i] == 0)
            continue;
        for (int j = 2; j*nums[i]&lt;=N; ++j) {
            nums[nums[i] * j] = 0;
        }
    }

    for (int i = M; i &lt;= N; ++i) {
        if (nums[i] != 0)
            std::cout &lt;&lt; nums[i] &lt;&lt; '\n';
    }
    
    return 0;
}</code></pre>
</div>
</div>

<h3 data-ke-size="size23">💡알게 된 것&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- <span>에라토스테네스의<span> 체<br>&nbsp;- 에라토스테네스는 천재인가? 그는 신인가?</span></span></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/1929
 
 문제 
 
 
 풀이 
 - 최대 범위가 1,000,000으로 주어졌으므로 에라토스테네스의 체를 사용해야 한다. 
O(Nlog(logN)) 의 시간복잡도를 가진다
 - 연산하기 쉽게 0에서 N까지 모두 벡터에 넣은 뒤 에라토스테네스의 체를 돌리며 소수가 아닌 수는 0으로 변경시킨다.
 - M에서 N사이의 0이 아닌 값을 출력한다.
 
 
☕코드는 아래 숨김
더보기
#include <iostream>
#include <vector>
#include <math.h>
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int M, N;
    std::cin >> M >> N;
    std::vector<int> nums(N+1, 0);
    for (int i = 0; i <= N; ++i) {
        nums[i] = i;
    }
    if (nums[1] == 1) {
       nums[1] = 0;
    }
    for (int i = 2; i <= std::sqrt(N); ++i) {
        if (nums[i] == 0)
            continue;
        for (int j = 2; j*nums[i]<=N; ++j) {
            nums[nums[i] * j] = 0;
        }
    }
    for (int i = M; i <= N; ++i) {
        if (nums[i] != 0)
            std::cout << nums[i] << '\n';
    }
    
    return 0;
}
 
 알게 된 것 
 - 에라토스테네스의 체
 - 에라토스테네스는 천재인가? 그는 신인가?

Beakjoon] 소수 구하기 (백준 1929 코테) - 정수론 (C++)

댓글