컨테이너에 여러 개의 금속 막대를 포장하는 작업의 수를 찾는 Python 프로그램

<시간/>

크기가 다른 여러 금속 막대를 운반하는 작업이 주어졌다고 가정합니다. 그러나 운송 컨테이너는 길이가 짧고 길이가 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_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
    - 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]