이 문제에서는 정수 N <=10^18이 주어집니다. 우리의 임무는 발생 빈도와 함께 숫자의 모든 소인수를 출력하는 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input: 100 Output: 2 2 5 2 Explanation: prime factorization of 100 = 2 * 2 * 5 * 5.
이 문제를 해결하려면 숫자의 소인수를 찾은 다음 빈도를 계산해야 합니다.
이를 위해 2의 빈도를 요소로 확인하고 숫자를 2로 나눕니다. 그런 다음 3에서 제곱근 n까지 확인합니다. 숫자의 인수인 각 소수의 빈도를 나누고 증가시킵니다. 그리고 숫자가 1이 되면 멈춥니다. 그런 다음 주파수가 있는 모든 소수를 인쇄합니다.
아래 코드는 우리 솔루션의 구현을 보여줍니다.
예시
#include <iostream>
#include <math.h>
using namespace std;
void factorize(long long n){
int count = 0;
while (!(n % 2)) {
n/= 2;
count++;
}
if (count)
cout<<2<<"\t"<<count<<endl;
for (long long i = 3; i <= sqrt(n); i += 2) {
count = 0;
while (n % i == 0) {
count++;
n = n / i;
}
if (count)
cout<<i<<"\t"<<count<<endl;
}
if (n > 2)
cout<<n<<"\t"<<1<<endl;
}
int main() {
long long N = 21000;
cout<<"The prime factors and their frequencies of the number "<<N<<" are \n";
factorize(N);
return 0;
} 출력
The prime factors and their frequencies of the number 21000 are 2 3 3 1 5 3 7 1