PS (C, C++)

[백준/C & C++] 1124 언더프라임

최연재 2023. 1. 28. 11:30

https://www.acmicpc.net/problem/1124

 

1124번: 언더프라임

자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다. 어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면,

www.acmicpc.net

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)

 

[백준/C & C++] 1929 소수 구하기

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.n

0yeonjae2.tistory.com

이제 반복문을 사용하여 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