<div id="readability-page-1" class="page"><div id="entry-view">
        
        <main>
          <section>
            <h2>소수 찾기</h2>
            <div>
              <article id="mainContent">
                
                <p><cite>honie</cite>
                  <span> 2023. 3. 8. 10:48</span>
                </p>
                                <div>
                                <h2 data-ke-size="size26"><span>소수?</span></h2>
<p data-ke-size="size16"><span>소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.</span></p>

<h3 data-ke-size="size23"><span>소수 찾는 방법</span></h3>
<p data-ke-size="size16"><span>1. n을 2부터 n-1로 나누었을 때 나누어지지 않으면 소수이다.</span></p>
<ul data-ke-list-type="disc">
<li><span>시간 복잡도 = $O(n)$ ※ 한개의 소수를 판단할 때의 시간 복잡도이다.</span></li>
</ul>
<pre><code>for i in range(2, n-1):
            if n % i == 0:
                print("소수가 아닙니다.")
                break
else:
    print("소수입니다.")
</code></pre>
<p data-ke-size="size16"><span>2.&nbsp;1번 방법은 2부터 $\ n-1$ 까지의 수 대입으로 속도가 느리다. 약수의 특징을 통해 효율적으로 접근해보면 $\sqrt{n}$ 까지의 수만 대입해봐도 약수의 여부를 알 수 있다.</span></p>
<ul data-ke-list-type="disc">
<li><span>약수는 대칭적인 형태를 띄는 것이 초점</span></li>
<li><span>N의 약수는 무조건 $\sqrt{n}$의 범위에 존재한다.</span></li>
<li><span>시간복잡도 = $O(\sqrt{n})$ ※ 한개의 소수를 판단할 때의 시간 복잡도이다.</span></li>
</ul>
<pre><code>for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                print("소수가 아닙니다.")
                break
else:
    print("소수입니다.")
</code></pre>
<p data-ke-size="size16"><span>3.&nbsp;<b>에라토스테네스의 체</b></span></p>
<ul data-ke-list-type="disc">
<li><span>어떤 특정한 수가 소수인지를 판단하기에는 좋은 방법이 아니다.</span></li>
<li><span>N이하의 소수가 몇개 있는지, 소수들을 직접 구하는 경우에 유용하게 쓰일 수 있다.</span></li>
<li><span>$\sqrt{n}$ 범위까지 지워지지 자신 제외 배수들을 전부 제거하는 방법</span></li>
<li><span>시간복잡도 = $O(nloglog{n})$</span></li>
</ul>
<pre><code>import math

n = 1000 
array = [True for i in range(n + 1)] # 범위내 전체수가 소수라 가정

for i in range(2, int(math.sqrt(n)) + 1): 
    if array[i] == True: 
        j = 2 # 자기 자신 제외 위해 2부터 시작
        while i * j &lt;= n:
            array[i * j] = False
            j += 1

# 모든 소수 출력
for i in range(2, n + 1):
    if array[i]:
        print(i, end=' ')
</code></pre>
            
            
                </div>
                            
            
              </article>
              
                
              
              
              
              
              
                
              
            </div>
          </section>
        </main>
        
      </div></div>

내일을 위해

Hunie

소수?
소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.
 
소수 찾는 방법
1. n을 2부터 n-1로 나누었을 때 나누어지지 않으면 소수이다.
시간 복잡도 = $O(n)$ ※ 한개의 소수를 판단할 때의 시간 복잡도이다.
for i in range(2, n-1):
            if n % i == 0:
                print("소수가 아닙니다.")
                break
else:
    print("소수입니다.")
2. 1번 방법은 2부터 $\ n-1$ 까지의 수 대입으로 속도가 느리다. 약수의 특징을 통해 효율적으로 접근해보면 $\sqrt{n}$ 까지의 수만 대입해봐도 약수의 여부를 알 수 있다.
약수는 대칭적인 형태를 띄는 것이 초점
N의 약수는 무조건 $\sqrt{n}$의 범위에 존재한다.
시간복잡도 = $O(\sqrt{n})$ ※ 한개의 소수를 판단할 때의 시간 복잡도이다.
for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                print("소수가 아닙니다.")
                break
else:
    print("소수입니다.")
3. 에라토스테네스의 체
어떤 특정한 수가 소수인지를 판단하기에는 좋은 방법이 아니다.
N이하의 소수가 몇개 있는지, 소수들을 직접 구하는 경우에 유용하게 쓰일 수 있다.
$\sqrt{n}$ 범위까지 지워지지 자신 제외 배수들을 전부 제거하는 방법
시간복잡도 = $O(nloglog{n})$
import math
n = 1000 
array = [True for i in range(n + 1)] # 범위내 전체수가 소수라 가정
for i in range(2, int(math.sqrt(n)) + 1): 
    if array[i] == True: 
        j = 2 # 자기 자신 제외 위해 2부터 시작
        while i * j <= n:
            array[i * j] = False
            j += 1
# 모든 소수 출력
for i in range(2, n + 1):
    if array[i]:
        print(i, end=' ')

소수 찾기

댓글