[프로그래머스] 숫자블록 #약수

https://programmers.co.kr/learn/courses/30/lessons/12923

코딩테스트 연습 - 숫자 블록

 

1. 풀이

위와 같은 규칙으로 블록을 설치하여 1번블록부터 10,000,000번 블록까지 규칙을 모두 적용하면 최종블록은 아래와 같다.

i	1	2	3	4	5	6	7	8	9	10	11	...
d[i]	0	1	1	2	1	3	1	4	3	5	1	...

이 블럭의 규칙은 바로 [ d[i]는 i의 약수중 자기자신을 제외한 가장 큰 숫자 ] 라는 것이다.

따라서 d[i]=i/(i의 약수 중 1을 제외한 가장 작은 숫자) 가 된다.

이때 주의할점은

(1) i가 소수(약수가 1or 자기자신)밖에 없는 경우에는 그냥 1을 넣어준다.

(2) 나누는수는 최대가 10,000,000이므로 j가 1~sqrt(end)까지 반복할때 i//j>10,000,000이면 continue

​

2. 소스코드

from math import sqrt
 
def solution(begin, end):
    result=[]
    
    for i in range(begin,end+1):
        if i==1:
            result.append(0)
            continue
        for j in range(2,int(sqrt(end)+1)):
            if i//j>10000000:
                continue
            if i%j==0:
                result.append(i//j)
                break
        else :
            result.append(1)
    return result