탐구활동 3

 입력된 어떤 양의 정수의 가장 큰 소인수를 출력하는 프로그램을 for 반복 구조를 사용하여 작성해 보자. (예를 들어 13195의 가장 큰 소인수는 29이다.)

 

해설

 수학적으로 생각해보면 소인수의 정의는 주어진 자연수를 나누어떨어뜨리는 소수인 약수를 말한다. 따라서 주어진 수를 나누어떨어뜨리면서 소수인 수 중 최댓값을 파악하면 된다. 1부터 큰 값으로 가면서 체크하면 굳이 최댓값을 판별하기 위해 노력할 필요없이 그냥 계속 값을 업데이트 해주면 된다. 따라서 1부터 큰 값으로 이동하면서 주어진 자연수를 나누어뜨리면서 소수인 수를 찾는데 반복횟수를 줄여주기 위해서 만약 소인수를 찾았다면 값을 업데이트해줌과 동시에 처음에 주어줬던 자연수를 해당 소인수로 나누어 처음 주어진 수의 크기를 계속 줄여나간다. 이렇게 하면 최종적으로 주어진 자연수의 소인수 중 최댓값을 찾을 수 있다.

 

코드

#include <iostream>

using namespace std;

bool isprime(int a)
{
	if(a<=3) return true;
	for(int i=2; i*i<=a; i++){
		if(a%i==0) return false;
	}
	return true;
}

int main()
{
	int n, mx = 1;
	scanf("%d", &n);
	
	for(int i=1; i<=n; i++){
		if(n%i==0 and isprime(i)){
			n/=i;
			mx = i;
		}
	}
	printf("%d\n", mx);
	
	return 0;
}