choyj1127   1년 전

코드를 어디서부터 어떻게 고쳐야할까요.

소인수의 개수는 어떻게 해야할지 몰라 임의로 정했습니다.

slah007   1년 전

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년 전

소수를 구하는 함수를 따로 또 계산하다가 괜히 시간초과가 나왔었네요

정말 감사합니다

댓글을 작성하려면 로그인해야 합니다.