[Python] 프로그래머스. 숫자 블록 (Level 4)

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

코딩테스트 연습 - 숫자 블록 | 프로그래머스

문제 조건이 어려운 건 아니지만, begin과 end의 숫자범위가 말해주듯 효율성이 관건인 문제.

 

문제 조건에 따르면, 특정 시점의 번호를 채울 수 있는 값의 우선순위는

해당 번호 % 2 == 0 인 경우 > 해당 번호 % 3 == 0인 경우 > 해당 번호 % 4 == 0 인 경우... 이다.

 

여기까지만 이해해도 정확성은 100% 달성이 가능하다.

 

효율성을 확인하는 핵심은 '해당 숫자가 소수인지 아닌지' 확인하는 것.

해당 숫자가 소수라면, 1과 자기 자신 이외에는 나누어떨어지는 수가 없다는 뜻이므로 해당 숫자의 위치에는 1을 넣어야 한다.

 

소수를 판별하는 방법 중 가장 효율적인 방법은 2부터 해당 숫자의 루트값까지를 순회하면서 해당 숫자 % 순회값 == 0인지 확인하는 것.