두 개의 숫자 START와 END가 주어져 하나의 숫자 범위를 정의합니다. 우리의 목표는 [START, END] 범위 안에서 소인수가 오직 2와 3뿐인 숫자를 찾아 그 개수를 구하는 것입니다.
이 문제는 START부터 END까지 숫자를 하나씩 순회하며 해결할 수 있습니다. 각 숫자에 대해 2 또는 3으로 나누어 떨어지는지 검사하고, 나누어 떨어지면 계속 나누어 값을 줄여갑니다. 어느 쪽으로도 나눌 수 없다면 반복문을 종료합니다. 최종적으로 값이 1로 줄어들었다면, 해당 숫자는 2와 3 외에 다른 소인수를 가지지 않는다는 뜻입니다.
구체적인 예시를 통해 이해해 보겠습니다.
입력 및 출력 예시
예시 1
입력:
START=20 END=25
출력:
소인수가 2와 3뿐인 숫자의 개수: 1
설명:
각 숫자의 소인수 분해:
20 = 2×2×5
21 = 3×7
22 = 2×11
23 = 1×23
24 = 2×2×2×3
25 = 5×5
이 중 24만이 2와 3을 소인수로 가집니다.
예시 2
입력:
START=1000 END=1500
출력:
소인수가 2와 3뿐인 숫자의 개수: 4
설명:
1024, 1152, 1296, 1458이 해당 범위에서 2와 3만을 소인수로 가지는 숫자들입니다.
풀이 접근 방식
- 정수형 변수 START와 END를 입력받아 탐색할 숫자 범위를 정의합니다.
twothreeFactors(int start, int end)함수는 범위를 매개변수로 받아, 2와 3만을 소인수로 가지는 숫자의 개수를 반환합니다.- 조건을 만족하는 숫자를 셀 변수
count를 0으로 초기화합니다. - for 반복문을 사용하여 i=start부터 i=end까지 범위 내의 모든 숫자를 순회합니다.
- 각 숫자 num=i에 대해 while 반복문으로 num이 2로 나누어 떨어지면(num%2==0) 2로 나눕니다.
- 그렇지 않고 3으로 나누어 떨어지면(num%3==0) 3으로 나눕니다. 둘 다 해당하지 않으면 while 반복문을 break로 종료합니다.
- while 반복문이 끝난 후 num이 1이라면 count를 1 증가시킵니다.
- 모든 반복이 끝나면 count에는 조건을 만족하는 숫자의 총 개수가 저장되어 있습니다.
- count 값을 결과로 반환합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int twothreeFactors(int start, int end){
// start가 1이면 카운트되지 않도록 2부터 시작
if (start == 1)
{ start++; }
int count = 0;
for (int i = start; i <= end; i++) {
int num = i;
while(num>1){
// 2로 나누어 떨어지면 2로 나눔
if(num % 2 == 0)
{ num /= 2; }
// 3으로 나누어 떨어지면 3으로 나눔
else if (num % 3 == 0)
{ num /= 3; }
else // 2와 3 모두로 나누어 떨어지지 않으면 종료
{ break; }
}
// num이 1이면 2와 3만이 소인수라는 의미
if (num == 1)
{ count++; }
}
return count;
}
int main(){
int START = 10, END = 20;
cout <<"소인수가 2와 3뿐인 숫자의 개수:"<< twothreeFactors(START,END);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
소인수가 2와 3뿐인 숫자의 개수: 3