ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 소인수분해 응용2
    algorism 2020. 1. 10. 17:36

    자연수 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
Designed by Tistory.