문제설명
그렙시에는 0으로 된 도로에 숫자 블록을 설치하기로 하였습니다. 숫자 블록의 규칙은 다음과 같습니다.
블록의 번호가 n 일 때, 가장 처음 블록은 n 2번째 위치에 설치합니다. 그다음은 n 3, 그다음은 n * 4, ...로 진행합니다.만약 기존에 블록이 깔려있는 자리라면 그 블록을빼고 새로운 블록으로 집어넣습니다.
예를 들어 1번 블록은 2,3,4,5, ... 인 위치에 우선 설치합니다. 그다음 2번 블록은 4,6,8,10, ... 인 위치에 설치하고, 3번 블록은 6,9,12... 인 위치에 설치합니다.
이렇게 3번 블록까지 설치하고 나면 첫 10개의 블록은 0, 1, 1, 2, 1, 3, 1, 2, 3, 2이됩니다.
그렙시는 길이가 1,000,000,000인 도로에 1번 블록부터 시작하여 10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다.
그렙시의 시장님은 특정 구간의 어떤 블록이 깔려 있는지 알고 싶습니다.
구간을 나타내는 두 수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열(리스트)을 return하는 solution 함수를 완성해 주세요.
풀이 & coment
거의 내가 푼 게 아님. 다른 사람 코드라고 봐도 무방.
이런 수학적인 문제는 흥미도 재미도 없어서 그런지 못해도 너무 못하는 듯.
+)다시 풀어도 몰랐음 ㅇ9ㅇ
이 문제의 규칙
1. 소수 = 1
2. 소수가 아니라면 약수 중의 가장 큰 수
이렇게 크게 2가지라 보면 되는데, 해당 인덱스의 소수인지 아닌지를 판단하기 위해 2~int(end**0.5)+1까지 for문을 돔. 이 때 소수임을 확인하면서 약수 중의 가장 큰 수를 구할 수 있음
✅ 약수 중의 가장 큰 수 = 약수 중의 가장 작은 수로 해당 값을 나눈 수의 몫
따라서 2번째 for 문을 돌면서(2부터) 해당 값/j == 0 이라면 몫을 answer에 추가 후 break,
2번째 for 문을 돌면서 break가 안걸렸다면(소수라면) answer에 1을 추가
코드
def solution(begin, end):
answer = []
for i in range(begin,end+1):
if i ==1: answer.append(0)
else:
for j in range(2,int(end**0.5)+1):
if i/j > 10 ** 7:
continue
if i%j ==0:
answer.append(i/j)
break
else:
answer.append(1)
return answer