https://www.acmicpc.net/problem/1124
C
#include <stdio.h>
#include <stdlib.h>
int factorization(int n)
{
int result=0;
for (int i = 2; i <= n; i++)
{
if (n % i == 0)
{
n /= i;
result++;
i = 1;
}
}
return result;
}
int main()
{
int a, b,m=2, cnt=0;
scanf("%d %d", &a, &b);
int* arr = (int*)malloc(sizeof(int) * (b+1));
for (int i = 2; i <= b; i++) arr[i] = 1;
for (int i = 2; i <= b; i++) if (arr[i] == 1) for (int m = 2; i * m <= b; m++) arr[i * m] = 0;
for (int i = a; i <= b; i++)
{
if (arr[i] == 1) continue;
else if (arr[factorization(i)] == 1) cnt++;
}
printf("%d", cnt);
free(arr);
return 0;
}
C++
#include <iostream>
#include <cstdlib>
using namespace std;
int factorization(int n)
{
int result = 0;
for (int i = 2; i <= n; i++)
{
if (n % i == 0)
{
n /= i;
result++;
i = 1;
}
}
return result;
}
int main()
{
int a, b, cnt = 0;
cin >> a >> b;
int* arr = new int[b + 1];
for (int i = 2; i <= b; i++) arr[i] = 1;
for (int i = 2; i <= b; i++) if (arr[i] == 1) for (int m = 2; i * m <= b; m++)arr[i * m] = 0;
for (int i = a; i <= b; i++)
{
if (arr[i] == 1) continue;
else if (arr[factorization(i)] == 1) cnt++;
}
cout << cnt;
delete[]arr;
return 0;
}
코드 설명
a, b를 입력받고 동적할당으로 b+1개의 원소를 가진 배열을 만든다. 에라토스테네스의 체를 이용하여 b까지 소수 판별을 한다. (에라토스테네스의 체를 이용한 문제 풀이 : https://0yeonjae2.tistory.com/m/entry/%EB%B0%B1%EC%A4%80C-1929-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0)
이제 반복문을 사용하여 a부터 b까지의 수를 소인수분해한다. 소수일 경우 언더프라임이 아니므로 continue;하고 소수가 아닐 경우에만 소인수분해를 진행한다.
factorization 함수는 소인수분해를 진행하고 소수의 목록의 길이를 반환하는 함수이다. 여기서 반환되는 값이 소수인지 확인하고 소수라면 cnt를 증가시킨다. 반복문이 끝나면 cnt를 출력하고 동적배열을 해제한 후 프로그램을 종료한다.
느낀 점
factorization 함수를 어떻게 구현해야 할지 고민했던 문제다. result를 증가시킨 후 다시 i=1를 해줘야 한다는 것을 파악한 뒤에는 금방 풀었다!
'PS (C, C++)' 카테고리의 다른 글
[백준/C & C++] 3273 두 수의 합 (0) | 2023.01.30 |
---|---|
[백준/C & C++] 2740 행렬 곱셈 (0) | 2023.01.29 |
[백준/C & C++] 1269 대칭차집합 (0) | 2023.01.27 |
[백준/C & C++] 1764 듣보잡 (0) | 2023.01.26 |
[백준/C & C++] 2477 참외밭 (0) | 2023.01.25 |