1.5.3 Superprime Rib 特殊的质数肋骨

code

6 年前

时间： 1ms 内存：64M

描述：

农民约翰母牛总是产生最好的肋骨。
你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。
农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说:
7 3 3 1
全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。
7331 被叫做长度 4 的特殊质数。
写一个程序对给定的肋骨的数目 N (1<=N<=8),求出所有的特殊质数。数字1不被看作一个质数。

输入：

单独的一行包含N。

输出：

按顺序输出长度为 N 的特殊质数,每行一个。

示例输入：

示例输出：

提示：

参考答案（内存最优[752]）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int isprime(int n)
{
	int i;
	if(n==2)
		return 1;
	if(n%2==0)
		return 0;
	for(i=3;i*i<=n;i+=2)
		if(n%i==0)
			return 0;
		
		return 1;
}

void sprime(int n, int ndigit)
{
	if(ndigit==0) 
	{
		printf("%d\n",n);
		return;
	}
	n*=10;
	if(isprime(n+1))
		sprime(n+1, ndigit-1);
	if(isprime(n+3))
		sprime(n+3, ndigit-1);
	if(isprime(n+7))
		sprime(n+7, ndigit-1);
	if(isprime(n+9))
		sprime(n+9, ndigit-1);
}
int main()
{
	int n;
    scanf("%d", &n);
	sprime(2, n-1);
	sprime(3, n-1);
	sprime(5, n-1);
	sprime(7, n-1);
	return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
#include <string>
#include<stdio.h>
 using namespace std;

int num1[4]={2,3,5,7};//高位
int num2[4]={1,3,7,9};//低位

int
isprime(int n)  //判断是否是素数
{
	int i;
	if(n == 2)
		return 1;
	if(n%2 == 0)
		return 0;

	for(i=3; i*i <= n; i+=2)
		if(n%i == 0)
			return 0;

		return 1;
}

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;
		}
	}
}

int main(){
	int N,p;
	int i;
	//freopen("sprime.txt","r",stdin);
	//freopen("sprime.out","w",stdout);
    scanf("%d",&N);
	for (i=0;i<4;i++){
		p=num1[i];
	    if (N==1)
			{printf("%d\n",num1[i]);}
        else
			dfs(p,0,N-1);
	}
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。