1. num이 소수인지 판정할 때 2 ~ num-1이 아니라 2 ~ sqrt(num)에 대해 조사하면 됩니다. 만약 sqrt(num)보다 큰 약수 p가 존재한다면 (num/p)는 sqrt(num)보다 작은 num의 약수이므로 앞에서 이미 걸러집니다. 실제 구현은 sqrt를 직접 구하지 않고 for(i=2;i*i<=num;i++)로 하는 것이 좋습니다.
2. 소인수분해를 할 때도 소수 판정과 비슷하게 역시 i = 2 ~ sqrt(num)까지만 봅시다.
a) 어떤 num을 나누는 i=p가 나왔다면 num에 있는 p를 모두 나눠주면 되는데, p는 반드시 소수입니다. 소수 판정도 필요 없습니다. 앞서서 p보다 작은 소수들로 나눠지는지를 모두 검사했기 때문에 p는 [2, p-1]에 약수가 없습니다.
b) 앞선 소수 판정과 마찬가지의 논리로 생각해 봅시다. i = 2 ~ sqrt(num)까지 보면서 나눌 수 있으면 나눈 뒤 남은 num은 1 또는 소수입니다. 즉 마지막에 남은 num>1이라면 그것까지 약수에 포함하면 됩니다.
choyj1127 1년 전
코드를 어디서부터 어떻게 고쳐야할까요.
소인수의 개수는 어떻게 해야할지 몰라 임의로 정했습니다.