'소인수분해'에 해당되는 글 2건

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

코드

#include <iostream>

using namespace std;

int main()
{   
    // :: 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

    // :: Input
    int number;
    cin >> number;

    // :: Exception
    if(number == 1) return 0;

    // :: Progress
    string result = "";
    for (int i = 2; i <= number; i++)
    {
        while (number % i == 0)
        {
            result += to_string(i) + "\n";
            number /= i;
        }
    }

    // :: Output
    cout << result;
    return 0;
}

참고

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

코드

using System;
					
public class Program
{
	public static void Main()
	{
		// :: 입력 : 소인수 분해할 것
		int num = int.Parse(Console.ReadLine());
		
		// :: EXIT : 1일 경우
		if(num == 1) return;
		
		// :: 소인수 분해
		string print = "";
		for(int index = 2; index <= num; index++) {
			// :: 0으로 나눠질 때
			if(num % index == 0) {
				// :: 나눈 것을 넣을 것
				num = num / index;

				// :: print에 소수 기록
				print += index.ToString();

				// :: 1이 되었으면 Break
				if(num == 1) {
					break;
				}
				// :: 아니면
				else {
					// :: 한줄 띄기 넣기
					print += "\n";
				}

				// :: 초기화
				index = 1;
			}
		}
		
		// :: 출력
		Console.WriteLine(print);
	}
	
	// :: 소수 구하기 : 이거 쓰면 시간 초과
	public static bool IsPrime(int num) {
		// :: 1이면 소수가 아님
		if(num == 1) return false;
		
		// :: 본래 수의 2를 나눈 것(제대로 이해는 안되지만, 반절까지)까지 나눴을 때 0이 되는 게 있는 지 확인
		for(int index = 2; index <= num / 2; index++) {
			if(num % index == 0) return false;
		}
		return true;
	}
}