C++의 배열에 있는 모든 합성 숫자의 곱

<시간/>

n개의 정수로 구성된 배열 arr[n]이 주어지면, 과제는 배열에 있는 모든 합성 숫자의 곱을 찾는 것입니다.

합성수는 다른 두 정수를 곱하여 만든 정수입니다. 예를 들어 6은 정수인 2와 3을 곱하여 만들 수 있는 합성수입니다. 또한 소수가 아니라고 말할 수 있습니다.

입력

arr[] = {1, 2, 4, 5, 6, 7}

출력

설명 - 배열의 합성 숫자는 4와 6이고 곱은 24입니다.

입력

arr[] = {10, 2, 4, 5, 6, 11}

출력

설명 - 배열의 합성 숫자는 10, 4, 6이고 곱은 240입니다.

문제를 해결하기 위해 다음과 같은 접근 방식을 사용합니다.

배열의 모든 요소를 반복합니다.
소수 또는 합성수가 아닌 숫자를 찾습니다. 즉, 1을 제외한 다른 숫자로 나눌 수 있습니다.
모든 합성 숫자를 곱하십시오.
결과를 반환합니다.

알고리즘

Start
Step 1→ Declare function to find the product of consecutive numbers in array
   int product_arr(int arr[], int size)
      declare int max = *max_element(arr, arr + size)
      set vector<bool> prime(max + 1, true)
      set prime[0] = true
      set prime[1] = true
      Loop For int i = 2 and i * i <= max and i++
         IF (prime[i] == true)
            Loop For int j = i * 2 and j <= max and j += i
               Set prime[j] = false
            End
         End
      End
      Set int product = 1
      Loop For int i = 0 and i < size and i++
         IF (!prime[arr[i]])
            Set product *= arr[i]
         End
      End
      return product
Stop

예시

#include <bits/stdc++.h>
using namespace std;
//function to find product of consecutive numbers in an array
int product_arr(int arr[], int size){
   int max = *max_element(arr, arr + size);
   vector<bool> prime(max + 1, true);
   prime[0] = true;
   prime[1] = true;
   for (int i = 2; i * i <= max; i++){
      if (prime[i] == true){
         for (int j = i * 2; j <= max; j += i)
            prime[j] = false;
      }
   }
   int product = 1;
   for (int i = 0; i < size; i++)
      if (!prime[arr[i]]){
         product *= arr[i];
      }
      return product;
}
int main(){
   int arr[] = { 2, 4, 6, 8, 10};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"product of consecutive numbers in an array: "<<product_arr(arr, size);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

product of consecutive numbers in an array: 1920