欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java素数代码(java判断素数最快方法)

程序员文章站 2023-11-21 11:13:52
经过一番艰难的思想斗争,觉得自己并不想学习网络,怀疑自己入错了坑!我想了很久想的我头晕目眩,想的我茶不思,饭不想;想的我不想再想;走路在想,上课在想,下课在想,睡觉在想,就连拉屎也不得不想,,最后还是...

经过一番艰难的思想斗争,觉得自己并不想学习网络,怀疑自己入错了坑!我想了很久想的我头晕目眩,想的我茶不思,饭不想;想的我不想再想;

走路在想,上课在想,下课在想,睡觉在想,就连拉屎也不得不想,,最后还是决定学习android开发,不管我的选择是否正确,何况本就没有正确一说,正确与错都只是那些成功者对我们诉说的故事而已!至少我现在不后悔,现在不会以后也不会,因为这就是我的选择;

而且就算是别人认为我错了那又怎么样,我不在乎再一次展示一下自己的狼狈;

现在什么也不想,什么也不说,什么也不干;一心一意学习此番;

希望假以时日,我也可以在别人迷茫的时候,可以坦然的写出自己的故事,然后甩下笔尖,悠然离去,而心中那一份精神却是无人能懂的,除非你亲自经历过,所以我不允许自己

相信任何人,只相信自己,任何人都不能阻挡我,包括我自己。而大部分时刻阻挡你的往往是你自己,如果你自己都不能阻挡你,则世无有所惧也!

——————————————————————————————————————————————————————————————————————————

大学大学,大部分靠自学,如果只学大纲的东西毕业后。那就是废物一条;

用此文开始我学android的过程!

——————————————————————————————————————————————————————————————————————————-

学习android开发首先要的java基础是一定要有的!

  1. <span style=”font-size:18px;”><span style=”font-size:14px;”>// 关于求1-n之间的素数用java实现的几种方法
  2. //1.常规方法 从2–x-1是否可以被整除
  3. package text;
  4. import java.util.scanner;
  5. public class test {
  6. public static void main(string[] args) {
  7. scanner in = new scanner(system.in);
  8. int x;
  9. x = in.nextint();
  10. boolean isprime = true;
  11. for (int i = 2; i <= x; i++) {
  12. for(int j = 2; j < i; j++) {
  13. if(i % j == 0) {
  14. isprime = false;
  15. break;
  16. }
  17. }
  18. if(isprime) system.out.print(i + ” “);
  19. isprime = true;
  20. }
  21. // 测试结果: 100
  22. // 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
  23. //
  24. }
  25. }</span>
  26. </span>

———————————————————————————————————————————————————————————————————————

  1. <span style=”font-size:18px;”>// 关于求1-n之间的素数用java实现的几种方法
  2. //2.改进方法 ①去偶数 ②从3开始每次加2是否可以被整除 则大约一共计算n/2次
  3. package text;
  4. import java.util.scanner;
  5. public class test {
  6. public static void main(string[] args) {
  7. scanner in = new scanner(system.in);
  8. int x;
  9. x = in.nextint();
  10. boolean isprime = true;
  11. for(int i = 1; i <= x; i++ ) {
  12. if(i == 1 || (i % 2 == 0 && i != 2 ) ) continue; //1和偶数便可以不必再往下走
  13. for(int j = 3; j < i; j += 2) {
  14. if(i % j == 0) { //如果是2则不进入子循环
  15. isprime = false;
  16. break;
  17. }
  18. }
  19. if(isprime) system.out.print(i + ” “);
  20. isprime = true;
  21. }
  22. // 测试结果: 100
  23. // 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
  24. //
  25. }
  26. }
  27. </span>

——————————————————————————————————————————————————————————————————————————

  1. <span style=”font-size:18px;”>// 关于求1-n之间的素数用java实现的几种方法
  2. //3.改进方法 每个数只要除到sqrtx 即可
  3. package text;
  4. import java.util.scanner;
  5. public class test {
  6. public static void main(string[] args) {
  7. scanner in = new scanner(system.in);
  8. int x;
  9. x = in.nextint();
  10. boolean isprime = true;
  11. for(int i = 1;i <= x; i++) {
  12. if(i == 1 || (i % 2 == 0 && i != 2)) continue;
  13. for(int j = 3;j <= math.sqrt(i);j += 2 ) {
  14. if(i % j == 0) {
  15. isprime = false;
  16. break;
  17. }
  18. }
  19. if(isprime) system.out.print(i + ” “);
  20. isprime = true;
  21. }
  22. // 测试结果: 100
  23. // 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
  24. //
  25. }
  26. }</span>

———————————————————————————————————————————————————————————————————————————–

  1. <span style=”font-size:18px;”>// 关于求1-n之间的素数用java实现的几种方法
  2. //4.改进方法 判断是否可以被<x的素数整除
  3. package text;
  4. import java.util.scanner;
  5. public class test {
  6. public static void main(string[] args) {
  7. scanner in = new scanner(system.in);
  8. int x;
  9. x = in.nextint();
  10. int[] prime = new int[100];
  11. int cnt = 1;
  12. prime[0] = 2;
  13. boolean isprime = true;
  14. for(int i = 3; i <= x; i += 2) {
  15. for(int j = 0; j < cnt; j++) {
  16. if(i % prime[j] == 0) {
  17. isprime = false;
  18. break;
  19. }
  20. }
  21. if(isprime) prime[cnt++] = i;
  22. isprime = true;
  23. }
  24. for(int k = 0; k < cnt; k++) {
  25. system.out.print(prime[k] + ” “);
  26. }
  27. // 测试结果: 100
  28. // 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
  29. //
  30. }
  31. }
  32. </span>


————————————————————————————————————————————————————————————————————————-5. 构造素数序列primes[i]: 2, 3, 5, 7, …

由4的算法我们知道, 在素数序列已经被构造的情况下, 判断n是否为素数效率很高;

但是, 在构造素数序列本身的时候, 是否也可是达到最好的效率呢?

事实上这是可以的! — 我们在构造的时候完全可以利用已经被构造的素数序列!

假设我们已经我素数序列: p1, p2, .. pn

现在要判断pn+1是否是素数, 则需要(1, sqrt(pn+1)]范围内的所有素数序列,

而这个素数序列显然已经作为p1, p2, .. pn的一个子集被包含了!

  1. // 关于求1-n之间的素数用java实现的几种方法
  2. //4.改进方法 构造素数表的方法
  3. <span style=”font-size:18px;”>package text;
  4. import java.util.scanner;
  5. public class test {
  6. public static void main(string[] args) {
  7. boolean[] isprime = new boolean[100];
  8. for(int i = 0;i < isprime.length; i++)
  9. isprime[i] = true;
  10. for(int i = 2; i < isprime.length;i++) {
  11. if(isprime[i]){
  12. for(int k = 2; i * k < isprime.length;k++){
  13. isprime[i * k] = false;
  14. }
  15. }
  16. }
  17. for(int i = 2; i < isprime.length; i++)
  18. if(isprime[i]) system.out.print(i + ” “);
  19. // 测试结果: 100
  20. // 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
  21. //
  22. }
  23. }
  24. </span>

最后自己总结一下;如果用数组做的话构造素数表的方法,个人觉得并不可取,因为假如要求的是1-x的素数而x很大,,那么必然要使用一个超大的数组而素数只是占其中一小部分,所以浪费了很多的空间;

2.建议采用第三种和第四种方法来做