[기초수학] 약수와 소수

[개념]

• 어떤 수를 나누어 떨어지게 하는 수를 약수라고 하고
• 1과 자신만을 약수로 가지는 수를 소수라고 합니다. (단, 1은 소수가 아니다.)

---

[ 실습 1 ] 소수 찾기

def is_decimal(num):
    if num <= 1:           # 0,1 관련 예외 처리
        return False
    for i in range(2,int(num**(1/2)+1)):
        if num%i==0:
            return False
    return True

for i in range(31):
    if is_decimal(i):
        print(i, end=' ')

# 2 3 4 5 6 7 8 9 11 13 15 17 19 23 25 29

 

코드 해석

 

num이 주어졌을 때,

num이 0 또는 1 또는 2 일 때 예외 처리하였습니다. ( 0, 1은 소수가 아니고, 2는 소수 )

2를 예외처리한건 num이 2일 때, 바로 밑에 for문에서 num이 2로 나누어지기 때문에 약수 처리되기 때문입니다.

( 첨엔 이 부분을 생각하지 못했고, 디버깅 하다 발견하였습니다. )

 

2일때는 예외처리 할 필요가 없었다.

범위를 range( 2, int(num**(1/2))+1 ) 로 하면

num 이 2일 때, range(2,2)로 아무것도 iterate하지 않기 때문에 굳이 예외처리 할 필요가 없었다.

 

그 후 2부터 차례대로 num을 나눠보고, 만약 추가적인 약수를 발견할 경우

이는 소수가 아님을 알 수 있고

 

num의 sqrt 값 까지 (소수 첫째 자리에서 내림함) 나눠봤음에도 불구하고 약수를 발견하지 못할 경우

소수 임을 알 수 있습니다.

 

---

[실습 2] 1부터 30까지 숫자 중 5로 나눈 몫과 나머지가 모두 소수인 숫자들

 

# 1부터 30까지 숫자 중 5로 나눈 몫과 나머지가 모두 소수인 숫자들
def is_decimal(num):
    if num <= 1:
        return False
    for i in range(2,int(num**(1/2))+1):
        if num%i==0:
            return False
    return True

for num in range(1,31):
    if is_decimal(num%5) and is_decimal(num//5):
        print(num, end = ' ')

# 12 13 14 17 18 19 22 23 24 27 28 29

위에서 만든 소수 찾기 함수를 응용하여 문제를 해결하였습니다.

 

---

실습 3. 소수와 합성수 찾기

numbers = int(input())
for number in range(2,numbers+1):
    flag=True
    for i in range(2,int((number)**(1/2)+1)):
        if number % i == 0:
            flag = False
            break
    if flag :
        print('{}는 소수'.format(number))
    else :
        print('{}는 \t\t 합성수'.format(number))

'''
30
2는 소수
3는 소수
4는              합성수
5는 소수
6는              합성수
7는 소수
8는              합성수
9는              합성수
10는             합성수
11는 소수
12는             합성수
13는 소수
14는             합성수
15는             합성수
16는             합성수
17는 소수
18는             합성수
19는 소수
20는             합성수
21는             합성수
22는             합성수
23는 소수
24는             합성수
25는             합성수
26는             합성수
27는             합성수
28는             합성수
29는 소수
30는             합성수
'''

코드 설명

앞전에 했던 소수찾기와 마찬가지로 

자기 자신과 1을 제외한, number보다 작은 수 중에서 나눠지는 수가 있으면 합성수

나눠지는 수가 없으면 소수로 분류했습니다.