imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:37Z

New page

* 그때 zp에서 소수 빨리 구하는 방법을 했던 적이 있더래죠. 난 그런거 뭐하러 하나 했는데..;;
* 뼈저리게 느껴집니다. 알고리즘의 중요성을..
* 테스트 해서 5초 넘기면 다시 짜오라네요. 첨에 소수 걍 아무렇게나 구해서 냈더니.. 한 천만쯤 가니까 어이없는 시간이 나오더군요..;; 그래서 소수의 성질 생각해서 이리저리 뜯어 고치다가 별 이상한 방법으로 9개 테스트 모두 5초 이내 통과 했습니다. ㅠ.ㅠ 마지막 테스트는 4.9xXX초 라는;;--;

#include <iostream>
#include <string>
#include <fstream>
#include <cmath>
using namespace std;

ifstream fin("pprime.in");
ofstream fout("pprime.out");

void InputMinMax(int& n, int& m);
string IntConvertToString(int n);
bool IsPrime(const int& n);
bool IsPalinDromes(const string& str);
void OutputResult(const int& n, const int& m);
void FillPrimeList(const int& n, const int& m);

int main()
{
int max,min;
InputMinMax(min, max);
OutputResult(min,max);

return 0;
}

void InputMinMax(int& min, int& max)
{
fin >> min;
fin >> max;
}

void OutputResult(const int& min, const int& max)
{
int init;

if(min<7)
init = 5;
else
init = (min/6)*6 + 1;

bool flag[3] = {false,};

for(int i = init ; i <=max ;)
{
if(IsPalinDromes(IntConvertToString(i)))
{
if(IsPrime(i))
{
fout << i << endl;
}
}
int temp;
if(i >= 1000 && !flag[0])
{
temp = 9997;
flag[0] = true;
}
if(i >= 100000 && !flag[1])
{
temp = 999997;
flag[1] = true;
}
if(i >= 10000000 && !flag[2])
{
temp = 99999997;
flag[2] = true;
}

if(flag[0] && flag[1] && flag[2])
i = temp;

if(i%6==1)
i += 4;
else if(i%6==5)
i += 2;
}
}

string IntConvertToString(int n)
{
int maxlessn ;
string ret;
for(int i = 1 ; i <= 100000000 ; i *= 10)
{
if(i > n)
{
maxlessn = i/10;
break;
}
}

for(int i = maxlessn ; i >= 1 ; i /= 10)
{
int t = n / maxlessn;
n -= maxlessn * t;
maxlessn /= 10;
ret += (char)t + 48;
}

return ret;
}

bool IsPalinDromes(const string& str)
{
if( (str.length() % 2 == 0) && str.length() < 2)
return false;
int n = str.length()/2;
for(int i = 0 ; i < n ; i++)
{
if( str[i] != str[str.length() - i - 1] )
return false;
}
return true;
}

bool IsPrime(const int& n)
{
if(!(n%2))
return false;
for(int i = 3 ; i <= sqrt(n) ; i+=2)
{
if(!(n%i))
return false;
}
return true;
}

［Lovely］boy＾ ＾/USACO/PrimePalinDromes - Revision history

imported>Unknown at 05:28, 7 February 2021

［Lovely］boy＾＾/USACO/PrimePalinDromes - Revision history