소수 구하기 with 파이썬

소수 구하기¶

• 소수랑 1과 자신만을 약수로 가지는 수 이다.
• 소수는 컴퓨터로 자료를 암호화할때 사용된다.

우리가 17이 소수인지 판별하기 위해 가장 쉬운 방법으로는

2,3,4,~16까지 나누어 지는지 확인하면 된다.

즉 나머지가 0인지 여부를 판별하면 된다.

이를 코딩으로 구현해보자.

[1]소수이면 'x는 소수이다', 아니면 'x는 소수가 아니다'를 출력하면서 해보자.¶

• 우선 소수의 판별: 기본적인 알고리즘을 보자. (Python)
• 소수의 개념을 이해하면서, 간단한 코딩을 만들어보자.
• 3은 소수 인가? 아닌가? 소수이다.

In [121]:

x = 3
x_prime = True                  # True는 '참'이라는 의미이며 초기값을 참으로 정의
for i in range(2,x):            # 2부터 자기자신 -1까지의 수에대해
    if x % i == 0:              # x를 i로 나눈 나머지가 0이면, 
        x_prime = False         # x_prime을 '거짓'의 의미인 False로 바꾸어라

if x_prime == True:
    print ('{}는 소수이다.'.format(x))  # 소수이다를 출력하라
else:
    print ('{}는 소수가 아니다.'.format(x))

3는 소수이다.

• 위 코드를 응용해서 코딩함수의 결과값으로 소수이면 'True', 거짓이면 'False'를 리턴하게 만들어보자.

In [122]:

def is_prime(x):
    a = range(2, x)  #2부터 x-1까지의 list
    b = 0
    for i in a:    
        if x % i == 0:  
            b += 1   
    if b > 0:
        print ('{}는 소수가 아니다.'.format(x))
        c = False   
    else:
        print ('{}는 소수이다.'.format(x))      
        c = True
    return c

In [123]:

is_prime(3)

3는 소수이다.

Out[123]:

True

In [124]:

is_prime(27)

27는 소수가 아니다.

Out[124]:

False

In [125]:

is_prime(516)

516는 소수가 아니다.

Out[125]:

False

[2]이제 2부터 100 사이의 모든 소수 구하기를 해보자.¶

• 소수란 1과 자신만을 소수로 가지는 수 를 이용하여 코딩 #### ex) 1

In [126]:

# 2~100 사이의 모든 소수 구하기 
num = 2
while num <= 100:
    count = 0  # 약수의 개수를 세어줄 변수
    i = 1  # 1~num까지 증가할 변수
    while i <= num:
        if num % i == 0:  # 나누어지면 약수
            count += 1
        i += 1  # 1증가
    if count == 2:  # 약수의 개수가 2개면 출력
        print('{0}의 약수가 {1}개이므로 "소수"입니다.'.format(num, count))

    num += 1  # 100까지 증가

2의 약수가 2개이므로 "소수"입니다.
3의 약수가 2개이므로 "소수"입니다.
5의 약수가 2개이므로 "소수"입니다.
7의 약수가 2개이므로 "소수"입니다.
11의 약수가 2개이므로 "소수"입니다.
13의 약수가 2개이므로 "소수"입니다.
17의 약수가 2개이므로 "소수"입니다.
19의 약수가 2개이므로 "소수"입니다.
23의 약수가 2개이므로 "소수"입니다.
29의 약수가 2개이므로 "소수"입니다.
31의 약수가 2개이므로 "소수"입니다.
37의 약수가 2개이므로 "소수"입니다.
41의 약수가 2개이므로 "소수"입니다.
43의 약수가 2개이므로 "소수"입니다.
47의 약수가 2개이므로 "소수"입니다.
53의 약수가 2개이므로 "소수"입니다.
59의 약수가 2개이므로 "소수"입니다.
61의 약수가 2개이므로 "소수"입니다.
67의 약수가 2개이므로 "소수"입니다.
71의 약수가 2개이므로 "소수"입니다.
73의 약수가 2개이므로 "소수"입니다.
79의 약수가 2개이므로 "소수"입니다.
83의 약수가 2개이므로 "소수"입니다.
89의 약수가 2개이므로 "소수"입니다.
97의 약수가 2개이므로 "소수"입니다.

• 임의의 수를 2부터 나누어질 때까지 반복하고, 나누어 졌을때 자기 자신이면 중간에 약수가 없는것. (즉 소수이다.) #### ex) 2

In [127]:

# 2~100 사이의 모든 소수 구하기 
num = 2
count = 0  # 소수의 개수를 세어줄 변수
while num <= 100:
    i = 2  # 2 ~ num 까지 증가할 변수
    while num % i:  # 나누어질 떄까지 반복
        i += 1      # 1증가

    if i == num:  # 나누어진 수가 자기 자신이면 소수
        print('{0:5}'.format(num), end='')
        count += 1
        if not count % 10:  # 개수가 10의 배수면 줄바꿈
            print()
    num += 1  # 100까지 증가

    2    3    5    7   11   13   17   19   23   29
   31   37   41   43   47   53   59   61   67   71
   73   79   83   89   97

[3]마지막으로는 알고리즘을 개선하는 과정¶

ex) 개선 전¶

In [128]:

# 소수 판별 함수(2이상의 자연수에)
def is_prime_number(x):
    # 2부터 (x - 1)까지의 모든 수를 확인
    for i in range(2, x):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

In [129]:

print(is_prime_number(6)) # 6는 소수가 아님

False

In [130]:

print(is_prime_number(3)) # 3은 소수

True

소수의 판별을 보니, 알고리즘의 성능도 같이 나온다. (계산하는데 알고리즘이 걸리는 시간) 개선해보자.¶

• 2부터 𝑋의 제곱근(소수점 이하 무시)까지의 모든 자연수에 대하여 연산 수행

ex) 개선 후¶

In [131]:

import math

# 소수 판별 함수
def is_prime_number(x):
    # 2부터 x의 제곱근까지의 모든 수를 확인
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

In [132]:

print(is_prime_number(6)) # 6는 소수가 아님

False

In [133]:

print(is_prime_number(3)) # 3은 소수

True

• Reference:
  • 프리라이프의 기술 블로그
  • 중학 수학 코딩의 정석
  • WikiDocs