소수 찾기

소수?

소수는 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=' ')