크기가 다른 여러 금속 막대를 운반하는 작업이 주어졌다고 가정합니다. 그러나 운송 컨테이너는 길이가 짧고 길이가 1인 막대만 포함할 수 있습니다. n개의 막대가 제공되고 그 길이가 목록에 표시됩니다. 따라서 컨테이너에 있는 모든 막대를 맞춥니다. 모든 막대를 자르고 나누어 단위 크기가 되도록 해야 합니다. 또한 한 번의 작업으로 모든 막대를 컨테이너에 넣습니다. 막대에서 수행해야 하는 작업의 수를 찾아야 합니다.
따라서 입력이 input_arr =[6, 3, 7]과 같으면 출력은 22
가 됩니다.-
크기 6의 막대를 크기 1의 막대로 만들려면 10번의 작업을 수행해야 합니다.
-
크기 3의 막대를 크기 1의 막대로 만들려면 4번의 작업을 수행해야 합니다.
-
크기 7의 막대를 크기 1의 막대로 만들려면 8번의 작업을 수행해야 합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
Prime_find() 함수를 정의합니다. input_num
이 필요합니다.-
Prime_check :=True 값을 포함하는 ((input_num-1)/2)의 크기 하한 값의 새 목록
-
(input_num) +1의 제곱근의 바닥까지 범위 3에 있는 p_num에 대해 2만큼 증가, 수행
-
Prime_check[(p_num-3)/2의 하한 값]이 0이 아닌 경우
-
(p_num ^ 2-3)/2에서 prime_check의 p_num까지의 범위 하한 값에 있는 각 요소에 대해
-
Prime_check[element] :=False 값을 포함하는 크기의 새 목록(((input_num-p_num ^2)/(2*p_num) + 1)의 바닥 값)
-
-
-
-
범위 0에서 (input_num - 1) / 2의 하한 값에 있는 i에 대해
- prime_check[i]가 참인 경우 -
-
값 2 + 2 * i + 3을 포함하는 목록을 반환
-
- prime_check[i]가 참인 경우 -
-
-
주요 기능에서 다음을 수행하십시오 -
- prime_nums :=prime_find(10^6 + 100)
- 결과:=0
- input_arr의 각 값에 대해 다음을 수행합니다.
- 결과 :=결과 + 값
- f_list :=새 목록
- prime_nums의 각 p_num에 대해 다음을 수행합니다.
- mod p_num 값이 0인 동안 do
- f_list 끝에 p_num 삽입
- 값 :=(값 / p_num)의 하한값
- p_num^2> 값이면
- 값> 1이면
- f_list 끝에 값 삽입
- 루프 종료
- 값> 1이면
- mod p_num 값이 0인 동안 do
-
- 온도 :=1
- f_list의 각 p_num에 대해 역순으로 수행합니다.
- 결과 :=결과 + 온도
- temp :=temp * p_num
- 반환 결과
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from math import floor,sqrt def prime_find(input_num): prime_check = [True]*((input_num-1)//2) for p_num in range(3,floor(sqrt(input_num))+1,2): if prime_check[(p_num-3)//2]: prime_check[(p_num**2-3)//2::p_num] = [False] * ((input_num-p_num**2)//(2*p_num) + 1) return [2]+[2*i+3 for i in range((input_num - 1) // 2) if prime_check[i]] def solve(input_arr): prime_nums = prime_find(10**6+100) result = 0 for value in input_arr: result += value f_list = [] for p_num in prime_nums: while value % p_num == 0: f_list.append(p_num) value //= p_num if p_num**2 > value: if value > 1: f_list.append(value) break temp = 1 for p_num in f_list[-1::-1]: result += temp temp *= p_num return result if __name__ == "__main__": print(solve([6, 3, 7]))
입력
[6, 3, 7]
출력
22