양의 정수 N이 주어집니다. 목표는 N을 0으로 줄이는 데 필요한 연산의 수를 찾는 것입니다. 적용된 연산은 N=N-P이고 여기서 P는 P의 가장 작은 소수입니다.
예를 들어 이해하자
입력 - N=17
출력 − N을 0으로 줄이는 데 필요한 주어진 유형의 연산 수는 − 1
설명 − 17의 가장 작은 소수는 17 자체입니다. 따라서 작업은 17-17=0에 한 번만 적용됩니다.
입력 - N=20
출력 − N을 0으로 줄이는 데 필요한 주어진 유형의 연산 수는 − 10입니다.
설명 − 20의 가장 작은 약수는 2입니다. 2를 계속해서 빼고 다음 소수를 찾는 방법:
20%2==0, 20-2=18 18%2==0, 18-2=16 …………………..14, 12, 10, 8, 6, 4, 2, 0 Total 10 times the operation is applied.
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
모든 짝수 N의 가장 작은 약수는 항상 2이고 짝수 N에서 2를 빼면 다시 짝수가 됩니다. 모든 홀수의 경우 가장 작은 소수는 홀수이고, 홀수에서 홀수를 빼면 숫자가 다시 짝수가 되어 2가 가장 작은 소수가 됩니다. 가장 작은 소수를 찾으려면 i*i
정수 N을 입력으로 받습니다.
N_to_Zero(int N) 함수는 N을 취하고 N을 0으로 줄이는 데 필요한 연산 수를 반환합니다.
count의 초기값을 0으로 합니다.
i=2부터 시작합니다. (i*i)
(i*i)가 N을 초과하면 i=N으로 설정합니다.
작업 수는 1+(N-i)/2입니다.
카운트를 1+(N-i)/2로 설정합니다.
결과로 카운트를 반환합니다.
위의 코드를 실행하면 다음 출력이 생성됩니다 -
예시
#include<bits/stdc++.h>
using namespace std;
int N_to_Zero(int N){
int count = 0;
int i = 2;
while((i * i) < N && (N % i)){
i++;
}
if((i * i) > N){
i = N;
}
count = 1 + (N-i)/2;
return count;
}
int main(){
int N = 10;
cout<<"Count of operations of the given type required to reduce N to 0 are: "<<N_to_Zero(N);
return 0;
} 출력
Count of operations of the given type required to reduce N to 0 are: 5