USACO : Prime Palindromes


its silly to write such a huge code
my approach was pretty simple
i’ve got the idea from given hints
my code generates all the palindrome numbers from digit 1 to 8
better to say odd_palindrome numbers
because, if the last digit is even then it’s not prime, except 2
/*
ID: tausiq11
PROG: pprime
LANG: C++
*/

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

vector <int> oddPalindromeList;

void oneDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) oddPalindromeList.push_back (i);
}

void twoDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) oddPalindromeList.push_back (i * 10 + i);
}

void threeDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) 
			oddPalindromeList.push_back (100 * i + 10 * j + i);
	}
}

void fourDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) 
			oddPalindromeList.push_back (1000 * i + 100 * j + 10 * j + i);
	}
}

void fiveDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) {
			for ( int k = 0; k <= 9; k++ )
				oddPalindromeList.push_back (10000 * i + 1000 * j + 100 * k + 10 * j + i);
		}
	}
}

void sixDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) {
			for ( int k = 0; k <= 9; k++ )
				oddPalindromeList.push_back (100000 * i + 10000 * j + 1000 * k + 100 * k + 10 * j + i);
		}
	}
}

void sevenDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) {
			for ( int k = 0; k <= 9; k++ ) {
				for ( int l = 0; l <= 9; l++ ) 
					oddPalindromeList.push_back (1000000 * i + 100000 * j + 10000 * k + 1000 * l + 100 * k + 10 * j + i);
			}
		}
	}
}

void eightDigit ()
{
	for ( int i = 1; i <= 9; i += 2 ) {
		for ( int j = 0; j <= 9; j++ ) {
			for ( int k = 0; k <= 9; k++ ) {
				for ( int l = 0; l <= 9; l++ ) 
					oddPalindromeList.push_back (10000000 * i + 1000000 * j + 100000 * k + 10000 * l + 1000 * l + 100 * k + 10 * j + i);
			}
		}
	}
}

void generatePalinDrome ()
{
	oneDigit ();
	twoDigit ();
	threeDigit ();
	fourDigit ();
	fiveDigit ();
	sixDigit ();
	sevenDigit ();
	eightDigit ();
}

bool isPrime (int p)
{
	if ( p % 2 == 0 || p < 1 ) return false;

	int len = sqrt (p * 1.0);

	for ( int i = 3; i <= len; i += 2 ) if ( p % i == 0 ) return false;
	return true;
}

int main ()
{
	generatePalinDrome ();

	freopen ("pprime.in", "r", stdin);
	freopen ("pprime.out", "w", stdout);

	int a, b;
	scanf ("%d %d", &a, &b);

	for ( size_t i = 0; i < oddPalindromeList.size (); i++ ) {
		if ( oddPalindromeList [i] >= a && oddPalindromeList [i] <= b ) {
			if ( isPrime (oddPalindromeList [i]) ) printf ("%d\n", oddPalindromeList [i]);
		}
	}

	return 0;
}

// @END_OF_SOURCE_CODE

One thought on “USACO : Prime Palindromes

  1. USER: [tausiq11]
    TASK: pprime
    LANG: C++
    
    Compiling...
    Compile: OK
    
    Executing...
       Test 1: TEST OK [0.000 secs, 3028 KB]
       Test 2: TEST OK [0.011 secs, 3028 KB]
       Test 3: TEST OK [0.000 secs, 3028 KB]
       Test 4: TEST OK [0.011 secs, 3028 KB]
       Test 5: TEST OK [0.000 secs, 3028 KB]
       Test 6: TEST OK [0.000 secs, 3028 KB]
       Test 7: TEST OK [0.032 secs, 3028 KB]
       Test 8: TEST OK [0.032 secs, 3028 KB]
       Test 9: TEST OK [0.022 secs, 3028 KB]
    
    All tests OK.
    YOUR PROGRAM ('pprime') WORKED FIRST TIME!  That's fantastic
    -- and a rare thing.  Please accept these special automated
    congratulations.
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s