Massive Algorithms: Prime Palindromes

primepalindromes - codetrick
The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .

PROGRAM NAME: pprime

INPUT FORMAT

Line 1:

Two integers, a and b

SAMPLE INPUT (file pprime.in)

5 500

OUTPUT FORMAT

The list of palindromic primes in numerical order, one per line.

SAMPLE OUTPUT (file pprime.out)

5  7  11  101  131  151  181  191  313  353  373  383

http://leonlu.iteye.com/blog/1125554
找出a和b间既对称既是素数的数。
用递归去解这题。初始数据为单个的0-9和双数的00-99，扔进递归里每次在两边加0-9再递归，直到过长（大于b的长度）。这样每次递归的参数都可能是要的数值，所以递归方法首先要检查是否满足条件，除了要检查是否是素数、是否在[a,b]之间，还要注意有前导零的是不符合条件的。
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/pprime.java


	private static List<Integer> res = new ArrayList<Integer>();
	private static String[] init = new String[]{
	"0","1","2","3","4","5","6","7","8","9",
	"00","11","22","33","44","55","66","77","88","99"
	};
	private static int a;
	private static int b;
	private static String bstr;

	public static void main(String[] args) throws IOException {
	BufferedReader in = new BufferedReader(new FileReader("pprime.in"));
	PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
	"pprime.out")),true);

	// read data
	StringTokenizer st = new StringTokenizer(in.readLine());
	a = Integer.parseInt(st.nextToken());
	b = Integer.parseInt(st.nextToken());
	bstr = Integer.toString(b);

	// solve
	for(String s : init)
	dfs(s);
	Collections.sort(res);

	// output
	for(Integer num : res)
	out.println(num);
	System.exit(0);
	}

	private static void dfs(String n){
	// check and record
	checkAndRecord(n);

	// no further
	if(n.length() + 2 > bstr.length())
	return;

	for(int i = 0; i <= 9; i ++){
	String tmp = i + n + i;
	dfs(tmp);
	}
	}

	private static void checkAndRecord(String n){
	int tmp = Integer.parseInt(n);

	// min a = 5, eliminate some numbers obviously not prime
	if(tmp % 2 ==0 \|\| tmp %3 == 0) return;

	// out of range
	if(tmp < a \|\| tmp > b)
	return;
	// has leading zero
	if(Integer.toString(tmp).length() != n.length())
	return;

	// is not prime
	for(int i = 5; i*i <=tmp; i+=2){
	if(tmp %i == 0)
	return;
	}
	res.add(tmp);
	}

X. generate palindrome first then check whether they are prime.
http://jackneus.com/programming-archives/prime-palindromes/

bool isPrime(int num){

    int mx = sqrt(num) + 1;

    for(int i = 2; i < mx; i++){

        if(num % i == 0) return false;

}

    return true;

}

vector<int> palindromes;

int main(){

    ifstream in("pprime.in");

    ofstream out("pprime.out");

    int a, b;

    in >> a >> b;

    palindromes.push_back(5);

    palindromes.push_back(7);

    for(int d0 = 1; d0 < 10; d0 += 2){ //2-digit palindromes

        palindromes.push_back(10 * d0 + d0);

}

    for(int d0 = 0; d0 < 10; d0++){ //3-digit/4-digit palindromes

        for(int d1 = 1; d1 < 10; d1 += 2){

            palindromes.push_back(100 * d1 + 10 * d0 + d1); //3 digit

            palindromes.push_back(1000 * d1 + 100 * d0 + 10 * d0 + d1); //4 digit

}

}

    for(int d0 = 0; d0 < 10; d0++){ //5-digit/6-digit palindromes

        for(int d1 = 0; d1 < 10; d1++){

            for(int d2 = 1; d2 < 10; d2 += 2){

                palindromes.push_back(10000 * d2 + 1000 * d1 + 100 * d0 + 10 * d1 + d2);

                palindromes.push_back(100000 * d2 + 10000 * d1 + 1000 * d0 + 100 * d0 + 10 * d1 + d2);

}

}

}

    for(int d0 = 0; d0 < 10; d0++){ //7-digit/8-digit palindromes

        for(int d1 = 0; d1 < 10; d1++){

            for(int d2 = 0; d2 < 10; d2++){

                for(int d3 = 1; d3 < 10; d3 += 2){

                    palindromes.push_back(1000000 * d3 + 100000 * d2 + 10000 * d1 + 1000 * d0 + 100 * d1 + 10 * d2 + d3);

                    palindromes.push_back(10000000 * d3 + 1000000 * d2 + 100000 * d1 + 10000 * d0 + 1000 * d0 + 100 * d1 + 10 * d2 + d3);

}

}

}

}

    sort(palindromes.begin(), palindromes.begin() + palindromes.size());

    for(int i = 0; i < palindromes.size(); i++){

        if(a <= palindromes[i] && palindromes[i] <= b && isPrime(palindromes[i])) out << palindromes[i] << endl;

}

}

http://blog.csdn.net/u013451221/article/details/45047649

const int maxn = 20005;
int a,b;
int cnt = 0;
int prime[maxn];
bool is_prime(int v){
int e = sqrt(v) + 1;
for(int i = 2; i <= e; i++)
if(v % i == 0) return false;
return true;
}
int solve1(){ //1 2
for(int i = 1; i <= 9; i++){
int v1 = i;
int v2 = i * 10 + i;
if(is_prime(v1)) prime[cnt++] = v1;
if(is_prime(v2)) prime[cnt++] = v2;
}
}
int solve2(){//3 4
for(int i = 1; i <= 9; i++){
for(int j = 0; j <= 9; j++){
int v1 = i * 100 + j * 10 + i;
int v2 = i * 1000 + j * 100 + j * 10 + i;
if(is_prime(v1)) prime[cnt++] = v1;
if(is_prime(v2)) prime[cnt++] = v2;
}
}
}
int solve3(){//5 6
for(int i = 1; i <= 9; i++){
for(int j = 0; j <= 9; j++){
for(int k = 0; k <= 9; k++){
int v1 = i * 10000 + j * 1000 + k * 100 + j * 10 + i;
int v2 = i * 100000 + j * 10000 + k * 1000 + k * 100 + j * 10 + i;
if(is_prime(v1)) prime[cnt++] = v1;
if(is_prime(v2)) prime[cnt++] = v2;
}
}
}
}
int solve4(){//7 8
for(int i = 1; i <= 9; i++){
for(int j = 0; j <= 9; j++){
for(int k = 0; k <= 9; k++){
for(int l = 0; l <= 9; l++){
int v1 = i * 1000000 + j * 100000 + k * 10000 + l * 1000 + k * 100 + j * 10 + i;
int v2 = i * 10000000 + j * 1000000 + k * 100000 + l * 10000 + l * 1000 + k * 100 + j * 10 + i;
if(is_prime(v1)) prime[cnt++] = v1;
if(is_prime(v2)) prime[cnt++] = v2;
}
}
}
}
}
void init(){
solve1();solve2();solve3();solve4();
sort(prime,prime + cnt);
}

http://greenmoon55.com/usaco-prime-palindromes/
Read full article from primepalindromes - codetrick

Prime Palindromes - USACO 1.5.2

PROGRAM NAME: pprime

INPUT FORMAT

SAMPLE INPUT (file pprime.in)

OUTPUT FORMAT

SAMPLE OUTPUT (file pprime.out)

Labels

Popular Posts