java判斷素數最快方法「java素數代碼」

經過一番艱難的思想鬥爭，覺得自己並不想學習網絡，懷疑自己入錯了坑！我想了很久想的我頭暈目眩，想的我茶不思，飯不想；想的我不想再想；

走路在想，上課在想，下課在想，睡覺在想，就連拉屎也不得不想，，最後還是決定學習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.建議採用第三種和第四種方法來做