📄문제
임의의 N에 대하여 N!은 1부터 N까지의 곱을 의미한다. 이는 N이 커짐에 따라 급격하게 커진다. 이러한 큰 수를 표현하는 방법으로 소수들의 곱으로 표현하는 방법이 있다. 먼저 소수는 2, 3, 5, 7, 11, 13... 순으로 증가함을 알아야 한다. 예를 들면 825는 (0 1 2 0 1)로 표현이 가능한데, 이는 2는 없고 3은 1번, 5는 2번, 7은 없고, 11은 1번의 곱이라는 의미이다. 101보
다 작은 임의의 N에 대하여 N 팩토리얼을 이와 같은 표기법으로 변환하는 프로그램을 작성해보자. 출력은 아래 예제와 같이 하도록 한다.
⬇️ 입력
첫 줄에 자연수 N(3<=N<=1000)이 입력된다.
5 |
⬆️ 출력
소수의 곱으로 표현한다.
5! = 3 1 1 |
📝 풀이
#include <iostream>
using namespace std;
static bool primeArr[1001];
static int primes[1001];
int isPrime(int x);
void divide(int x);
int main()
{
for (int i = 0; i < 1001; ++i)
primes[i] = primeArr[i] = 0;
int N;
scanf_s("%d", &N);
printf("%d! = ", N);
for (int i = 2; i <= N; ++i)
divide(i);
for (int i = 2; i <= N; ++i)
if (primeArr[i])
printf("%d ", primes[i]);
}
void divide(int x)
{
int primeIdx = isPrime(x);
if (primeIdx == -1) // 소수가 맞음
{
++primes[x];
}
else if (x >= 2) // 소수가 아닌경우, 나누기
{
divide(x / primeIdx);
divide(primeIdx);
}
}
int isPrime(int x)
{
// 이미 소수로 등록되어있다면, 즉시 리턴
if (primeArr[x])
return -1;
// 해당 값으로 나눌것이 있어 소수가 아님
for (int i = 2; i <= sqrt(x); ++i)
if (x % i == 0)
return i;
// 소수를 검출하지 못한경우, x는 소수가 맞음
primeArr[x] = true;
return -1;
}
- 주어진 자연수가 소수인지 확인한 후, 소수라면 primes에 추가합니다.
- 소수가 아니라면, 나누어지는 값과 분리하여 재귀로 호출하여 소수가 될때까지 분해한 후 primes에 추가하도록 합니다.
'algorithms (C++)' 카테고리의 다른 글
[C++] 3의 개수 (small) (0) | 2023.10.14 |
---|---|
[C++] N!에서 0의 개수 🔥 (0) | 2023.10.13 |
[C++] 마라톤 (0) | 2023.10.13 |
[C++] 석차 구하기 (0) | 2023.10.13 |
[C++] Jolly Jumpers(유쾌한 점퍼) (0) | 2023.10.13 |