大家好,又见面了,我是你们的朋友全栈君。 Java算法——判断素数,供自己学习方便和初学者参考!
java算法初学之求素数 1、代码 import java.util.ArrayList; import java.util.List; /* * 求1-1024的素数 * 素数:只能被1和本身整除...3、算法思想 for循环遍历2到1024的数字,定义一个boolean作为标记。i++,j--。 如果j能被i整除,则bool标记为false,结束此循环。...最后foreach循环遍历list即可得到1到1024之间的素数。
灵机一闪,思绪回到了大二算法课上,老师讲过一种叫做“筛法”的东东,不过好像记不太清了,我再想想… 半分钟后… 回来了,我感到它们全都回来了!...嗯…毫不留情,莫非还有更优的算法? “您容我再想想哈~”,陪着笑脸说完,双手抱头痛苦思考状/(ㄒoㄒ)/~~ 我的神呐…还有啥,还能怎么筛?...咋一看,算法阐述起来和普通的筛法并无二致,实际上,两者最重要的区别就在于: 有无重复筛除? 为什么有这个问题呢?...)证明这个算法的时间复杂度和正确性,要从以下两个方面: 每个数至少被访问一次 对于质数,一定会在 $i$ 的循环中访问到,并确定为质数。...因此整个算法的复杂度是 $O(n)$ 的。 面试结果 ---- hmmmmmmmm… 当然,很愉快的,即使是在面试官迟到了1小时的情况下,TT还是很给面子,没让我过,我记住了,哼!
import java.util.Scanner; public class sum { //此方法判断传入的数是否为素数 static boolean is_prime(int n)...n % i == 0) return false; } return true; } //这是一个main方法,是程序的入口...} ans = 0; for (int i = a; i <= b; i++) { //判断此数是否为素数...} //打印 System.out.println();//换行 System.out.println("素数有...:" + ans);//计算素数个数 } } }
实现功能:如题,筛出1——N内的所有素数 原理:如phile神犇所言,这次的才算是真正意义上的线性筛素数,其精髓在于if (i mod a[j])=0 then break; 因为——如果眼下的a[j]...已经是i的因数了,则意味着即使再进行b[i*a[j]]:=1,那么I*b[j]也必然会被其他的数以同样的操作覆盖到,所以可以退出了,这个算法的思想在于减少重复劳动(鸣谢qcgrxx神犇,源链接) 1
资源限制 时间限制:1.0s 内存限制:512.0MB 编写一函数IsPrime,判断某个大于2的正整数是否为素数。...样例输入: 5 样例输出: yes 样例输入: 9 样例输出: no 注意:是素数输出yes,不是素数输出no,其中yes和no均为小写。...import java.util.*; public class sushupanduan { /** * @param args */ public static void main(String
求1+(1+2)+(1+2+3)+···+(1+2+3+···+10)的值?...h+=2; System.out.println(""); } } /** * 6.输出100到1000个位为3的所有素数...} for(int i=3;i<=Math.sqrt(1000);i+=2){ if(prime[i]){//如果他是素数...,他的倍数全部排除 for(int j=i+i;j<1000;j+=i){ prime[j]=false;
/*本程序就是建立一个素数程序*/ #include #include #define N 100 /*int prime(int n) { int i; for(...(n%i)) return 0; return 1; } void main(void) { int k; printf("%d以内的素数为:\n",N); for(k=
1 package test ; 2 import java.util.Scanner ; 3 public class hello 4 { 5 public static void...(); 11 int maxn=Integer.parseInt(rr); 12 boolean isprime[] = new boolean [maxn] ; //Java
:对于上边穷举遍历暴力的方法,判断一个正整数是否为素数。...所需的时间复杂度是O(n),然而在实际应用中,判断某一个数字是否为为素数只是整个程序当中的一小部分,这样的时间复杂度相对而言还是比较高的。...下面将一种时间复杂度为O(n^(1/2))时间复杂的判断素数的算法。 数学背景:对于任意一个正整数N,可以将其分解为两个因数。特殊情况下N^(1/2)相等,即N=N^(1/2)*N^(1/2)。...进过这样的 处理可以显著的降低判断是否为质数算法的时间复杂度,达到O(n^(1/2))。...:从小到大遍历每一个数字,将其倍数筛去,剩下的即为素数。
来源:labuladong 作者:labuladong 素数的定义很简单,如果一个数如果只能被 1 和它本身整除,那么这个数就是素数。...不要觉得素数的定义简单,恐怕没多少人真的能把素数相关的算法写得高效。...首先你用isPrime函数来辅助的思路就不够高效;而且就算你要用isPrime函数,这样实现也是存在计算冗余的。 先来简单说下如果你要判断一个数是不是素数,应该如何写算法。...我们可以稍微优化一下,让j从i的平方开始遍历,而不是从2 * i开始: for (int j = i * i; j < n; j += i) isPrim[j] = false; 这样,素数计数的算法就高效实现了...其最终结果是 O(N * loglogN),有兴趣的读者可以查一下该算法的时间复杂度证明。 以上就是素数算法相关的全部内容。怎么样,是不是看似简单的问题却有不少细节可以打磨呀?
java判断素数 本教程操作环境:windows7系统、java10版,DELL G3电脑。...1、判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除,则表明此数不是素数,反之是素数。 sqrt是指平方,其作用是提高操作速度,或者不使用。... main(String[] args) { int count=0; for (int i=101;i<=200;i++) { //数的范围... count++; System.out.println(i); } } System.out.println("素数的个数..."); else System.out.println(n+"不是素数"); } 以上就是java判断素数的方法,我们通过sqrt和计算器两种方法,都能得到对素数的判断结果,大家看懂后也来尝试一下吧
return False for i in range(2,num): if num%i==0: return False return True //arr为列表类型,求出1-100之间的素数
预计阅读时间:5 分钟 素数的定义很简单,如果一个数如果只能被 1 和它本身整除,那么这个数就是素数。 不要觉得素数的定义简单,恐怕没多少人真的能把素数相关的算法写得高效。...首先你用 isPrime 函数来辅助的思路就不够高效;而且就算你要用 isPrime 函数,这样实现也是存在计算冗余的。 先来简单说下如果你要判断一个数是不是素数,应该如何写算法。...首先,回想刚才判断一个数是否是素数的isPrime函数,由于因子的对称性,其中的 for 循环只需要遍历[2,sqrt(n)]就够了。...我们可以稍微优化一下,让j从i的平方开始遍历,而不是从2 * i开始: for (int j = i * i; j < n; j += i) isPrim[j] = false; 这样,素数计数的算法就高效实现了...其最终结果是 O(N * loglogN),有兴趣的读者可以查一下该算法的时间复杂度证明。 以上就是素数算法相关的全部内容。怎么样,是不是看似简单的问题却有不少细节可以打磨呀? 反向思考方能出其不意!
大家好,又见面了,我是全栈君 chuanbindeng 的 素数推断算法 关于素数的算法是信息学竞赛和程序设计竞赛中常考的数论知识,在这里我跟大家讲一下寻找一定范围内素数的几个算法。...} 这就是最一般的求解n以内素数的算法。复杂度是o(n*sqrt(n)),假设n非常小的话,这样的算法(事实上这是不是算法我都怀疑,没有水平。...在程序设计竞赛中就必需要设计出一种更好的算法要求能在几秒钟甚至一秒钟之内找出n以内的全部素数。于是就有了素数筛法。 (我表达得不清楚的话不要骂我,见到我的时候扁我一顿我不说一句话。。。)...上面的素数筛法是全部程序设计竞赛队员都必须掌握的,而后面加了两个优化的筛法是效率非常高的算法,是湖南大学 huicpc39同学设计的(可能是学来的,也可能是自创的。相当强悍)。...这上面的全部的素数筛选的算法都能够再进一步化为二次筛选法,就是欲求n以内的素数,就先把sqrt(n)内的素数求 出来,用已经求得的素数来筛出后面的合数。
大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说java判断是否为素数(质数)的方法,希望能够帮助大家进步!!!...质数的定义: 对于大于1的数,如果除了1和它本身,它不能再被其它正整数整除,那么我们说它是一个质数。...判断一个数是否为质数(素数)方法: 如果是偶数,直接返回;然后从3开始,步长为2,一直到n的算术平方根为止,都除不尽则为质数。...Java程序:(推荐:java视频教程) public class Main { public static void main(String[] args) { for (int j =
1-n组成的素数环,素数环就是一个数组中后一个数加前一个数必须组成素数,a[i]+a[i-1]是素数,又因为是环状所以,首末相加也要上素数即a[0]+a[n-1]是素数,因为是环状所以会有很多重复的排列...,我们要除去重复的排列,就要假定所有的排列都以1打头。...我们也是用回溯加剪枝来求素数环 #include #include using namespace std; unsigned char visit[100]...是否用过,和dfs一样 char prime[] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0};//0-32的素数表...prime_ring(int *arry,int cur,int n) { if(cur == n && is_prime(arry[0]+arry[n-1])) //如果排满了再判断一下末尾的和开头的是否能组成素数
题目 题目:求100之内的素数 2.
回文素数 ?...思路:从2开始枚举,然后先判断素数再判断回文数,判断素数用经典的根号算法就够了,之后回文数的判断就是将数字转字符串、将其反转判断是不是和原来相等,找100个这样的数字输出就好 /** * * @
1、遍历2以上N的平方根以下的每一个整数,是不是能整除N 1 bool Isprimer(int n) 2 { 3 int flag=1; 4 if (n<2) 5...flag) 17 return true; 18 else 19 return false; 20 21 22 } 2、遍历2以上N的平方根以下的每一个素数...,是不是能整除N;(这个方法是上面方法的改进,但要求N平方根以下的素数已全部知道)
领取专属 10元无门槛券
手把手带您无忧上云