글 읽기 - 혹시 시간 복잡도를 더 낮출수 있는 방법이 있을까요?

gsgh3016 1년 전 0

제 코드는 밑에와 같은데 chat GPT에 질문해보니 에라토스테네스의 체를 사용하면 가장 빠르다고 합니다. 근데 chat GPT가 제시한 코드는 정답이 아니라서 직접 짰습니다. 혹시 에라토스테네스의 체를 활용해서 문제를 풀 수 있나요? 아니면 더 빠른 알고리즘이 존재하나요?

#include <iostream>
#include <vector>

std::vector<bool> isSelfNum(10001, true);

int nextNum(int num)
{
	return num + num / 1000 + num / 100 % 10 + num / 10 % 10 + num % 10;
}

void checkSelfNum(int num)
{
	int temp = nextNum(num);
	while (temp <= 10000)
	{
		if (isSelfNum[temp])
		{
			isSelfNum[temp] = false;
		}
		temp = nextNum(temp);
	}
}

int main()
{
	std::ios_base::sync_with_stdio(false);

	for (int i = 1; i <= 10000; i++)
	{
		checkSelfNum(i);
	}

	for (int i = 1; i <= 10000; i++)
	{
		if (isSelfNum[i])
		{
			std::cout << i << '\n';
		}
	}
	return 0;
}

hjroh0315 1년 전 0

에라토스테네스의 체를 쓸 필요가 없습니다. 오히려 쓰려고 하는 편이 더 복잡합니다. ChatGPT를 맹신하지 마세요.

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

문제

문제

출처

ICPC

혹시 시간 복잡도를 더 낮출수 있는 방법이 있을까요?

gsgh3016 1년 전 0

hjroh0315 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말