728x90
반응형
문제:
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
풀이 방법:
소수는 1과 자기 자신으로만 나누어지는 수이기 때문에 반복문을 사용해서 임의의 수 x가 소수인지 판별하는 방법은 2부터 x-1까지 나누어 보았을 때, 나머지가 생기지 않으면 된다. 따라서 다음과 같이 코드를 작성할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 | def solution(n): answer=[] cnt=1 while(cnt!=n): cnt+=1 prime=True for i in range(2,cnt): if cnt%i==0: prime=False break if prime: answer.append(cnt) return len(answer) | cs |
하지만 이 방법은 효율적이지 못한 방법이라 큰 수의 경우에는 통과를 하지 못한다.
그 이유는 2부터 x-1까지 검사하기 때문에 엄청 큰 소수 인 경우 x-1까지 반복해야하기 때문이다.
하지만 수학적으로 생각해보면 만약 어떤 수의 약수가 존재한다면 x-1까지 검사할 필요 없이 sqrt(x)까지만 검사를 해보아도 충분하다는 것을 알 수 있다.
따라서 위 코드를 다음과 같이 수정을 하였다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def solution(n): import math answer=[2] cnt=1 while(cnt!=n): cnt+=1 prime=True for i in range(2,math.ceil(math.sqrt(cnt))+1): if cnt%i==0: prime=False break if prime: answer.append(cnt) return len(answer) | cs |
math에 있는 루트 함수인 sqrt와 올림 함수인 ceil을 사용해서 범위를 잡아 주었다. 그러면 다음과 같이 큰 수의 경우에도 통과를 하는 것을 알 수 있다.
하지만 이 방법이 소수를 판별하는 문제에서 최적의 효율을 나타내지는 않는다. 소수를 판별하는 문제에서 가장 효율이 좋은 코드는 '에라토스테네스의 체' 원리를 사용하는 것이다. 소수가 1과 자기 자신으로 나누어 지는 수라고 가정하면 소수가 아닌 수는 임의의 소수 하나로 나눌 수 있다는 말이 된다. 따라서 2부터 x-1까지 나누어보는 것이 아닌 소수 배열을 만들어서 임의의 소수로 나누어 지지 않는다면 소수가 된다는 것이다. 다음은 에라토스테네스의 체 원리를 이용해 작성한 코드다.
1 2 3 4 5 6 7 8 9 10 11 12 13 | def solution(n): answer=[] for i in range(2,n+1): prime=True for j in answer: if i%j == 0: prime=False break elif j > i**(1/2): break if prime: answer.append(i) return len(answer) | cs |
다음
다음과 같이 더 빨리 통과함을 알 수 있다. 효율성 테스트에서는 더 빨리 통과한다는 것을 체감할 수 있다.
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 1.문자열 내 마음대로 정렬하기 (0) | 2019.02.07 |
|---|---|
| [Programmers]Lv 2.주식 가격 (0) | 2019.02.06 |
| [Programmers]Lv 2.쇠막대기 (0) | 2019.02.04 |
| [Programmers]Lv 1. 시저 암호 (0) | 2019.02.03 |
| [Programmers]Lv 2.프린터 (0) | 2019.02.02 |