글 읽기 - 시간초과 도와줄 고수님 ㅠ

sywang0202 5년 전 1

시간초과 도와줄 고수님 ㅠ 왜나는지 모르겠어요

#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

char buf[1000000];
int front = 0, back = 0, N = 0;
bool pal(int N)
{
	sprintf(buf, "%d", N);
	front = 0;
	back = strlen(buf) - 1;
	while (front < back)
	{
		if (buf[front] != buf[back])
		{
			return false;
		}
		else
		{
			++front;
			--back;
		}
	}
	return true;
}

int main(void)
{
	int p = 0;
	scanf("%d", &N);
	while (1)
	{
		if (N == 1 | N == 2)
		{
			printf("2");
			break;
		}
		p = 0;
		for (int i = 2; i*i <= N; i++)
		{
			if (N%i == 0)
			{
				for(int j=i*i; j<=N; j+=i)
				p = 1;
			}
		}
		if (p == 0)
		{
			if (pal(N))
			{
				printf("%d\n", N);
				break;
			}
			else
			{
				N++;
			}
		}
		else
		{
			N++;
		}
	}
	return 0;
}

djm03178 5년 전 2

매 수마다 판정을 하는 것보다, 에라토스테네스의 체를 사용하는 것이 빠릅니다.

사실 이 문제의 경우, 정수들 중 팰린드롬의 비율이 지극히 낮기 때문에 소수 판정보다 팰린드롬 판정을 먼저 하는 것만으로도 훨씬 빨라집니다.

sywang0202 5년 전 0

감사합니다.. 한번해볼게요 ㅠㅠ 좋은하루되세요

i5533m 3년 전 0

팰린드롬으로 찾고 소수판정하니까 시간초과 뜨네요ㅠㅠ

에라토스테네스로 그냥 1003001까지 소수판별 모두 해놓고 팰린드롬 찾는게 더 효율적일것 같아욤..

djm03178 3년 전 0

그건 소수 판정 로직에 문제가 있는 겁니다. 제대로 만드셨다면 아무리 비효율적으로 소수 판정을 해도 0.1초면 충분합니다.

i5533m 3년 전 0

루트시간에 소수판정을 했는데 안돼서 생각해보니까 에라토스테네스에서 사용한 vector을 전역변수로 사용하지 않고 팰린드롬 나올때마다 새로 vector을 생성해서 소수 판정해서 그런것같아요.

그러면 혹시 djm03178님은 팰린드롬이 나올때마다 array의 크기를 팰린드롬숫자만큼 늘려서 소수를 판별해준건가욤??

팰린드롬 찾고 소수 판정하는방법이 좋은거같아서 해보고싶은데 좀 어렵네유ㅠㅠ

djm03178 3년 전 0

에라토스테네스의 체를 쓰지 않고 바로 소수 판정을 했습니다. 2부터 n-1까지 다 나누어보아도 되고, sqrt(n)까지만 해보면 좀 더 빠릅니다.

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