蓝桥杯算法提高-特殊的质数肋骨 Java实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了蓝桥杯算法提高-特殊的质数肋骨 Java实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2288字,纯文字阅读大概需要4分钟。
内容图文
![蓝桥杯算法提高-特殊的质数肋骨 Java实现](/upload/InfoBanner/zyjiaocheng/643/d608e3b478ad4c0fb5ea2f44f0098ff5.jpg)
特殊的质数肋骨
农民约翰母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数。
例如有四根肋骨的数字分别是:7 3 3 1,那么全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。7331 被叫做长度 4 的特殊质数。
写一个程序对给定的肋骨的数目 N (1<=N<=8),求出所有的特殊质数。数字1不被看作一个质数。
输入格式:
单独的一行包含N。
输出格式:
按顺序输出长度为 N 的特殊质数,每行一个。
输入样例:
4
输出样例:
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
思路:
这道题开始我直接想要暴力遍历进行质数判断,但是最后两个测试点因为数据太大会超时。后面参考了https://blog.csdn.net/DyP__CSDN/article/details/104178656一个学长的博客,发现递归判断重一位到n位更为简单,例如7331,先判断7,然后73,然后733,最后7331。
递归函数用两个参数传入,一个判断是否为素数的x,一位是题目要求的数的长度length,如果长度等于n并且判断是素数则输出,小于n就进入循环判断(x*10+i)是否为素数,递归判断输出即可。
下面附上代码:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
import java.util.function.IntToDoubleFunction;
import javax.print.attribute.Size2DSyntax;
import javax.security.auth.x500.X500Principal;
import javax.swing.text.Highlighter;
import org.omg.PortableServer.ID_ASSIGNMENT_POLICY_ID;
public class Main{
static int n;
public static int fun(int x) { //判断素数的函数
int flag=0;
if(x==1)
flag=-1;
for (int i = 2; i <= Math.sqrt(x); i++) {
if(x%i==0)
{
flag=-1;
break;
}
}
return flag;
}
public static void dfs(int x,int length) { //递归输出函数
if(length>n) //满足长度时输出
{
System.out.println(x);
}
else {
for (int i = 1; i <= 9; i++) {
if(fun(x*10+i)==0)
{
dfs(x*10+i, length+1);
}
}
}
}
public static void main(String args[]) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
Scanner sc=new Scanner(System.in);
n=Integer.parseInt(br.readLine());
dfs(0, 1);
}
}
つばめのりゅう℡
发布了20 篇原创文章 · 获赞 0 · 访问量 250
私信
关注
内容总结
以上是互联网集市为您收集整理的蓝桥杯算法提高-特殊的质数肋骨 Java实现全部内容,希望文章能够帮你解决蓝桥杯算法提高-特殊的质数肋骨 Java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。