U E D R , A S I H C RSS

[Lovely]boy^_^/USACO/Prime Palin Dromes

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


~cpp 
#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;
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:37
Processing time 0.0086 sec