USACO 1.5 – Superprime Rib

superprimerib - codetrick
Butchering Farmer John's cows always yields the best prime rib. You can tell prime ribs by looking at the digits lovingly stamped across them, one by one, by FJ and the USDA. Farmer John ensures that a purchaser of his prime ribs gets really prime ribs because when sliced from the right, the numbers on the ribs continue to stay prime right down to the last rib, e.g.:

     7  3  3  1  

The set of ribs denoted by 7331 is prime; the three ribs 733 are prime; the two ribs 73 are prime, and, of course, the last rib, 7, is prime. The number 7331 is called a superprime of length 4.
Write a program that accepts a number N 1 <=N<=8 of ribs and prints all the superprimes of that length.
The number 1 (by itself) is not a prime number.

PROGRAM NAME: sprime

INPUT FORMAT

A single line with the number N.

SAMPLE INPUT (file sprime.in)

4  

OUTPUT FORMAT

The superprime ribs of length N, printed in ascending order one per line.

SAMPLE OUTPUT (file sprime.out)

2333  2339  2393  2399  2939  3119  3137  3733  3739  3793  3797  5939  7193  7331  7333  7393

http://mycodebattle.com/2014/09/usaco-1_5-superprime-rib/

首先有几个特殊的数字。

1. 1 9不能作为第一位。
2. 2只能作为第一位。

其余的数字都不行。

然后DFS即可。

const int num[] = {1, 2, 3, 5, 7, 9};

int str[10], n;

 

bool Check(int nm)

{

    for (int i = 2; i <= (int)sqrt(nm + 0.5); i++)

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

    return true;

}

 

void DFS(int curLen)

{

    int i, j;

    if (curLen == n)

    {

        int nm = 0;

        for (i = 0; i < n; i++) nm = nm * 10 + str[i];

        if (Check(nm)) printf("%d\n", nm);

        return;

    }

    for (i = 0; i < 6; i++)

    {

        if (curLen == 0)

            if (i == 0 || i == 5) continue;

        if (curLen != 0 && i == 1) continue;

        str[curLen] = num[i];

        int nm = 0;

        for (j = 0; j <= curLen; j++) nm = nm * 10 + str[j];

        if (!Check(nm)) continue;

        DFS(curLen + 1);

    }

}

这题也是用递归。初始的数只可能为{2,3,5,7}，递归时检查不是素数就退出，是的话for i = 0: 9 dfs(10*num+i)继续递归，如果位数到了N且是素数，则输出。 
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/sprime.java

	public class sprime { private static int N;
	private static int[] init = new int[]{2,3,5,7};
	private static BufferedReader in;
	private static PrintWriter out;
	public static void main(String[] args) throws Exception{
	in = new BufferedReader(new FileReader("sprime.in"));
	out = new PrintWriter(new BufferedWriter(new FileWriter("sprime.out")),true);
	N = Integer.parseInt(in.readLine());
	for(int i : init)
	dfs(i);
	System.exit(0);
	}
	private static void dfs(int n){
	// if not prime return
	if(n != 2 && n % 2 == 0) return;
	for(int i = 3; i * i <=n; i+=2){
	if(n % i == 0) return;
	}
	// if the length, then output
	if(Integer.toString(n).length() == N)
	out.println(n);
	for(int i = 0; i <=9; i++)
	dfs(10 * n + i);
	}
	}

http://greenmoon55.com/usaco-superprime-rib/

void search(long a,int depth)
{
    long temp;
    int i;

    if (depth==n)
    {
        printf("%ld\n",a);
        return;
    }
    for (i=1;i<10;i+=2)
    {
        temp=a*10+i;
        if (isprime(temp)) search(temp,depth+1);
    }
}

http://blog.csdn.net/finded/article/details/39452243

1.最高位（首位）只能是质数数字：2，3，5，7

2.其余低位（除了最高位）只能是1，3，7，9

3.n=1时，可以直接输出2，3，5 7

    然后，这个题的解法很多。这里，我是采用的深度搜索DFS-回溯法。搜索的边界条件十分重要，我做是感觉比较混乱。这就导致程序出错，写出来后又调试了很久。最后程序还是条理不清，可读性不强。

    DFS时有几个地方要特别注意：不同位的递归-最高位和其余位，每一位的递归-尝试该位所有可能的数，递归的深度-特殊质数的位数。编程的核心就在与如何把这些约束有机高效的组合在一起。

void dfs(int p,int n,int N){
    int i;
 for (i=0;i<4&&n<N;i++){ 
  p=p*10+num2[i];

  if (isprime(p)){
   n=n+1;
   if(n==N) printf("%d\n",p);
            else     dfs(p,n,N);

   n=n-1;p=p/10;
   continue;
  }
  else {
   p=p/10;
   continue;
  } 
 } 
}

Read full article from superprimerib - codetrick