• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

에라토스테네스의 체를 활용한 isPrime 함수

23.10.13 17:00 작성 조회수 229

1

선생님 소수와 관련된 문제라 에라토스테네스의 체 알고리즘을 이용하여 배열에 미리 소수에 대한 여부를 파악하여 저장해두었습니다. isPrime 함수는 단순히 해당 배열의 값이 true인지 false인지 리턴을 하는것이라, 함수 자체의 의미가 없어지는거 같은 느낌이 들어서요.

 

실제 코딩테스트에도 이와같이 작성해도 문제가 없을까요? 아니면 함수의 의미에 맞게 함수 내부적으로 연산을 수행해야 할까요?

 

#include <iostream>

bool isPrime(int x);
int reverse(int x);

// 에라토스테네스의 체 알고리즘
static bool primes[100001];

int main()
{
	int N, numInput;
	scanf_s("%d", &N);

	// 모두 true로 초기화
	for (int i = 0; i < 100001; ++i)
		primes[i] = 1;

	// 0과 1은 소수가 아님
	primes[0] = primes[1] = false;

	// 에라토스테네스의 체 알고리즘을 통해 모든 소수 판별
	for (int i = 2; i <= std::sqrt(100001); ++i)
	{
		if (!primes[i])
			continue;

		primes[i] = true;
		for (int j = i * 2; j < 100001; j += i)
			primes[j] = false;
	}

	// 나머지 계산
	for (int i = 0; i < N; ++i)
	{
		scanf_s("%d", &numInput);

		int reverseNum = reverse(numInput);
		if (isPrime(reverseNum))
			printf("%d ", reverseNum);
	}
}

bool isPrime(int x)
{
	return primes[x];
}

int reverse(int x)
{
	int num = 0;

	while (x > 0)
	{
		num = num * 10 + x % 10;
		x /= 10;
	}

	return num;
}

답변 1

답변을 작성해보세요.

1

안녕하세요^^

이 문제에서는 N제한이 100까지이지만 실제 코딩테스트에서 N제한이 많이 커진다면 위에 코드가 영상의 방법보다 더 효율적인 코드라 생각됩니다. 잘 하셨습니다.

Bonnate님의 프로필

Bonnate

질문자

2023.10.14

감사합니다 !!