파이썬 연습을 위해 연습문제를 2개 풀어보았다.
Q1. N 이하의 자연수에서 소수 찾는 함수
Q2. N 이하의 두 자연수의 합의 마지막자리가 4가 되는 수를 찾는 함수
먼저, 1번 문제는 'N 이하의 자연수에서 소수를 찾는 함수를 만들기' 이다.
이 문제는 3가지 방식으로 풀어보았는데 첫번째는 다음과 같다.
def find(x):
list = [i for i in range(2,x+1)]
for j in range(2,x+1):
for y in range(2,j):
if j % y == 0:
list.remove(j)
break
return list
처음 시도했던 방법인데, 처음에 list안에 숫자를 다 넣은 후 조건문을 걸어서 소수가 아닌 수는 리스트에서 제거되도록 했다.
아무래도 처음부터 리스트에 숫자를 다 넣고 시작하기 때문에 범위가 커질수록 데이터를 많이 차지해서 매우 느려진다.
다음으로 두 번째 풀이 식이다.
def find_2(x):
list = []
for j in range(2,x+1):
chk = True
for y in range(2,j):
if j % y == 0:
chk = False
if chk:
list.append(j)
return list1번 방법에서 처음부터 숫자를 다 넣고 시작하는 점 때문에 느린 점을 보완하기 위해, 두번째로 처음엔 빈 리스트로 시작해서 조건에 맞는 값만 리스트에 넣는 방식으로 풀어봤다.
그런데 원래 이렇게 하면 더 빨라질 줄 알았는데, 원인은 모르겠는데 두번째 방법이 훨씬 더 느리다...?
이건 코드를 내가 뭔가 이상하게 짰을 수도 있어서 일단 보류...
마지막 방법은 구글링하면 제일 많이 나오는 방식이다.
import math
def find_3(n):
arr = [True for i in range(n+1)]
for i in range(2, int(math.sqrt(n)) + 1):
if arr[i] == True: j = 2
while i * j <= n:
arr[i * j] = False
j += 1
for i in range(2, n+1):
if arr[i]: print(i, end=' ')세번째 방법은 이런 유형의 문제를 풀 때 구글링하면 제일 많이 나오는 에라토스테네스의 체 알고리즘이다.
기존 1,2번 방식은 n이하의 자연수에서 소수를 찾기 위해 n까지의 모든 자연수를 반복문으로 검색하는 방식이라면, 에라토스테네스의 체 알고리즘에서는 자연수의 약수에 존재하는 원리를 사용한다.
1과 자기자신을 제외한 약수가 존재하는지 확인하려면, 자기자신의 제곱근(루트)까지만 확인하면 되기 때문에 전체 숫자를 돌지 않고 해당 숫자의 제곱근까지만 반복문으로 확인하는 방식이다.
이렇게 되면 반복문을 도는 횟수를 현저히 줄일 수 있기 때문에 속도면에서 훨씬 효율적인 코드라고 할 수 있다.
다음 문제는 'N 이하의 두 자연수의 합의 마지막자리가 4가 되는 수를 찾는 함수를 만들기' 이다.
def find_4(x):
list = []
for i in range(x+1):
for j in range(x+1):
if (i+j)%10 == 4:
list.append((i,j))
return list
이 문제는 앞의 문제를 이미 풀었다면 쉽게 풀 수 있는 문제이다.
숫자 n이 주어졌을 때 그 수 이하의 두 자연수의 합의 마지막자리가 4가 되는지를 판별하려면, n이하의 무작위의 자연수 두개를 추출하여 더한 수를 10으로 나누었을 때 나머지가 4로 떨어지는지만 확인하면 되기 때문이다.
그렇게 나머지가 4가 되는 두 수의 조합을 튜플로 묶어서 한쌍으로 리스트에 넣어주도록 했다.
