약수 | 소수

약수

어떤 수를 나머지 없이 나눌 수 있는 자연수

 

약수 구하는 법

(1) 1 ~ n 까지 확인

(2) 1 ~ n/2 까지 확인

(3) 1 ~ n의 제곱근 까지 확인

ex) 16의 약수: 1, 2, 4, 8, 16

## n까지의 약수 리스트 생성
# (1)
divisor = []
for i in range(1, n+1):
    if n%i == 0:
        divisor.append(i)
        
divisor = [i for i in range(1, n+1) if n%i == 0]

# (2)
divisor = []
for i in range(1, n//2+1):
    if n%i == 0:
        divisor.append(i)
divisor.append(n)

divisor = [i for i in range(1, n//2+1) if n%i == 0] + [n]

# (3)
divisor = []
for i in range(1, int(n**(1/2))+1):
    if n%i == 0:
        divisor.append(i)
        if i != n//i:
            divisor.append(n//i)
            
# 주의할 점: 
# 위의 코드를 실행할 경우, 0의 결과는 [0], 1의 결과는 [1]

 

약수의 합

## 약수의 합
# for문 이용: divisor.append(i) -> result += i
result = 0
for i in range(1, n+1):
    if n%i == 0:
        result += i
        
# 리스트 컴프리헨션 이용: sum 함수
result = sum([i for i in range(1, n+1) if n%i == 0])

 

소수

2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수

 

기본 소수 판별법

## 기본 (n-1까지 확인)
for i in range(2, n):
    if n%i == 0:
        print("not prime")
        break
else:
    print("prime")
    
## 함수로 만들 경우
def prime(n):
    for i in range(2, n):
    	if n%i == 0:
        	return False
    return True
   
print(prime(10))
#result: False

 

제곱근까지 확인하는 소수 판별법

자연수의 경우 제곱근을 기준으로 대칭적으로 약수를 곱해 그 수를 만들 수 있음

ex) 16의 약수: 1, 2, 4, 8, 16 

-> 제곱근까지 확인하여 소수 판별 가능

## 제곱근까지 확인
# import math
# for i in range(2, int(math.sqrt(n))+1)
for i in range(2, int(n**(1/2))+1):
    if n%i == 0:
        print("not prime")
        break
else:
    print("prime")

 

에라토스테네스의 체를 이용한 소수 판별법

 

[에라토스테네스의 체]

(1) 2부터 n까지의 모든 자연수 나열

(2) 남은 수 중에서 가장 작은 수 i 선택

(3) 남은 수 중에서 i의 배수를 모두 제거

--> 더 이상 반복할 수 없을 때까지 (2) ~ (3) 반복

## 에라토스테네스의 체 이용
# 소수 판별
ls = [1 for i in range(n+1)] # [True for _ in range(n+1)]
ls[0], ls[1] = 0, 0 # 어차피 제외되기 때문에 굳이 없어도 되는 작업

for i in range(2, int(n**(1/2))+1):
    if ls[i] == 1: # ls[i] == True
        for j in range(1, n//i+1):
            ls[i*j] = 0
        if ls[n] == 0:
            print("not prime")
            break
else:
    print("prime")

 

자연수 n까지의 소수 리스트 생성 함수

# n까지의 소수 리스트 생성
def prime(n):
    ls = [1 for i in range(n+1)]
    for i in range(2, int(n**(1/2))+1):
        if ls[i] == 1:
            for j in range(2, n//i+1):
                ls[i*j] = 0
    return [i for i in range(2, n+1) if ls[i]]

prime(10)
#result: [2, 3, 5, 7]