https://www.acmicpc.net/problem/1747
입력
첫째 줄에 N이 주어진다.
출력
첫째 줄에 조건을 만족하는 수를 출력한다.
풀이
먼저 n은 1,000,000 이고
arr,n,i,j 는 long long 형으로 설정한다.
input size는 1004000이하 이다 왜냐하면 에라스토네의 체로 소수를 구한 후 100000보다 큰 소수 중 팰린드롬이 되는 수는 1003001이기 때문이다.
for (long long i = 2; i <= 1004000; i++)
{
arr[i] = i;
}
for (long long i = 2; i <= sqrt(1004000); i++)
{
if (arr[i] == 0)
continue;
for (long long j = i + i; j <= 1004000; j += i)
{
arr[j] = 0;
}
}
long long i = n;먼저 에라스토네의 체로 소수를 구하여 배열에 넣고
i를 n으로 설정한다.
이유는 n부터 팰린드롬이 되는 수를 구하는게 문제이기 때문.
while (true)
{
if (arr[i] != 0)
{
long long ans = arr[i];
if (isprendromll(ans))
{
cout << arr[i]<<"\n";
break;
}
}
i++;
}소수인 수 가운데서 최초로 팰린드롬이 되는 수가 발견되면 바로 출력 후 종료이다.
bool isprendromll(int prime)
{
string str = to_string(prime);
int start = 0;
int end = str.size() - 1;
while (start < end)
{
if (str[start] != str[end])
{
return false;
}
start++;
end--;
}
return true;
}팰린드롬인지 판별하는 함수
먼저 int로 받은 수를 string으로
to_string 함수로 변환
그 후 start,end 투 포인터로
서로 만날때까지 검사한다. 검사가 끝나면 TRUE 반환 팰린드롬 수 아닐 시 FASLE를 반환한다.
풀면서 나왔던 오류 -Run-Time Check Failure #2 - Stack around the variable 'arr' was corrupted.
선언한 변수 혹은 배열이 TYEP 또는 크기를 넘어갔을때 생기는 오류이다 나는 arr[1000040]으로 선언하고 for문은 1000400까지 돌려서 생긴 오류였다.
느낀점
팰린드롬 문제를 처음 경험해봤다.
생각보다 어렵지 않았다. 또한 int 형에서 string으로 변환하는 to_string 함수 string형에서 char로 변환 해주는 c._str() 함수의 존재를 알았다. c._str()함수는 char const* 형으로 변환해주어야 한다.
