-
자연수 N이 입력되면 N! 값에서 일의 자리부터 연속적으로 ‘0’이 몇 개 있는지 구하는 프로그 램을 작성하세요. 만약 5! = 5x4x3x2x1 = 120으로 일의자리부터 연속적된 ‘0’의 개수는 1입니다. 만약 12! = 479001600으로 일의자리부터 연속적된 ‘0’의 개수는 2입니다.
▣ 입력설명
첫 줄에 자연수 N(10<=N<=1,000)이 입력된다.
▣ 출력설명
소인수 분해한 결과를 출력한다.
▣ 입력예제 1
12
▣ 출력예제 1
2
int형은 2의 31 -1까지밖에 값을 수할수없습니다 따라서 N이 1000까지 N!를 구할수 없습니다
따라서 N까지의 숫자를 소인수 분해하여 소인수분해된 2의 갯수와 5의 갯수를 비교하여 다음문제를 해결해 나갈수 있다
#include<iostream> #include<vector> using namespace std; int main() { int two = 0; int five = 0; int j = 0; int tmp = 0; int N=0; cin >> N; vector<int> a(N+1); for (int i = 2; i <= N; i++) { tmp = i; j = 2; while (1) { if (tmp % j == 0) { if (j == 2)two++; else if (j == 5)five++; tmp = tmp / j; } else j++; if (tmp == 1) break; } }// 소인수분해 if (two < five)//2의 갯수와 5의 갯수를 비교하여 두개를 곱하여 만들수있는 10의 갯수를 구함 2의갯수가 2개 5의갯수가 3개다 그러면 5가 1개 더 많더라고 총 10을 2개밖에 만들지 못함 cout << two; else cout << five; }
'algorism' 카테고리의 다른 글
재귀함수 - 2진수출력 (0) 2020.01.10 재귀함수 알고리즘-STACK으로 (0) 2020.01.10 소인수 분해 응용 (0) 2020.01.10 초당 타이머 (0) 2020.01.10 마라톤 경주 (0) 2020.01.09