TIL - algorithm - 06

김영훈·2021년 3월 11일
0

# 소수 찾기

  • 오류 코드

    • 숫자 n이 주어졌을 때, 1부터 n 사이에 있는 소수개수를 구하는 문제

    • 소수가 1과 자신을 제외한 숫자로 나누어떨어지지 않는 수라는 점에서 착안하여 알고리즘을 만들었다.

    import time

    def solution(n):
        start = time.time()
    
        x = 0                         # 소수가 아닌 수의 개수를 변수 x에 할당
                            
        for i in range(1, n+1):       # for 반복문으로 1 이상 n 이하의 숫자를 대상으로 소수 여부를 판별

            if i == 1:                # 1은 소수가 아니므로 x값 1 증가
                x += 1

            if i == 2:                # 2는 소수이므로 continue를 통해 다음 loof로 건너뛴다.
                continue

            else:                     # 1과 2가 아닌 숫자 i를 대상으로 흐름 처리
                for j in range(2, i):  
                    if i % j == 0:    # 숫자 i가 1과 자신이 아닌 숫자j로 나눠 떨어지는 경우 -> 소수가 아님 
                        x += 1        
                        break         # 한 번 값이 추가되면 -> 소수가 아님이 증명됐으므로 -> 반복문 진행할 필요 없어진다.
                answer = n - x        # n - (소수가 아닌 수의 개수)
                
        end = time.time()
        print(end-start) 
        return answer
        
    print(solution(100000))
  • 문제점

    • 코드의 떨어지는 효율성으로 인해, 처리 속도가 느리다.

    • n값으로 100000을 지정했을 경우, 결괏값이 반환될 때까지 자그마치 18.47초가 걸린다.

  • 정답 코드

    • '에라토스테네스의 체'란 수학에서 사용되는 용어로 소수를 찾는 방법을 가리킨다. 고대 그리스의 수학자가 발견했다고 하는데, 쉽게 말해서 2부터(1은 소수가 아니므로 제외) 차례대로 소수를 찾은 뒤, 그 이후에 오는 소수의 수를 소거하는 방법이다. 이렇게 소거된 숫자를 제외하고 남은 수가 바로 1과 n 사이에 존재하는 모든 소수가 된다.

    • 아래의 코드가 바로 '에라토스테네스의 체'를 구현한 것이다.

    • 코드를 확인하고 들었던 생각은 두 가지다. 첫 번째는 정답 코드가 내 머리로는 생각해낼 엄두가 나지 않는 기발한 코드였다는 것이고, 다른 하나는 내가 생성한 코드보다 700배 이상의 효율을 자랑하는 정답 코드의 처리 속도를 체감함에 따라, 효율성 높은 코드의 중요성에 대해 다시 한번 깨달았다는 것이다.

    n=100000
    a = [False,False] + [True]*(n-1)     # 소수 판별의 대상은 2이상 n이하의 숫자이므로,
                                         # 리스트 안에 요소 True를 숫자 1을 제외한 (n-1)개로 설정한다.
    primes=[]                            # [Fasle,Fasle]를 추가한 이유:
                                         # 리스트 객체 a의 '인덱스 값'과 리스트 내의 인덱스에 해당하는 요소값 True가 '가리키는 숫자'를 일치시킴으로써 
                                         # 계산을 편리하게 하기 위해서...(뭔 소리지?) 
    for i in range(2,n+1):               # 가령, 인덱스2(i=2)에 해당하는 리스트 요소 True가 가리키는 숫자는 2이다.
        if a[i]:
            primes.append(i)
            for j in range(2*i, n+1, i): # a[i] == True인 경우, 해당 인덱스(i)의 배수에 해당하는 인덱스의 요소값을 모두 Fasle로 변경
                a[j] = False

    print(len(primes))                   # a[i] == True인 요소로 채워진 리스트 primes의 길이 = 소수의 개수
  • review

    • time 모듈의 time()를 사용하면 함수의 처리가 시작부터 완료되기까지 걸리는 시간측정할 수 있다.

    • range(start, stop, step)으로 숫자의 간격을 설정할 수 있다.

profile
Difference & Repetition

0개의 댓글