目錄
一、素數(shù)及相關(guān)概念
?1、素數(shù)的性質(zhì)
?2、有關(guān)素數(shù)的猜想
?二、素數(shù)的判斷方法
?1、根據(jù)性質(zhì)去判斷
?2、改進1方法（縮小比較范圍√n）
3、再次分析素數(shù)的特點，得出規(guī)律
問題：枚舉n以內(nèi)所有素數(shù)
?4、埃氏篩法（埃拉托斯特尼篩法）
5、歐拉篩法（埃氏篩法的優(yōu)化版）
三、素數(shù)相關(guān)題目
一、素數(shù)及相關(guān)概念
素數(shù)又稱質(zhì)數(shù)。一個大于1的自然數(shù)，除了1和它自身外，不能被其他自然數(shù)整除的數(shù)叫做素數(shù)；否則稱為合數(shù)（規(guī)定1既不是質(zhì)數(shù)也不是合數(shù)）。
?1、素數(shù)的性質(zhì)
- 質(zhì)數(shù)只有兩個因數(shù)：1和本身。
- 任何大于1的自然數(shù)，要么本身是質(zhì)數(shù)，要么可以分解為幾個質(zhì)數(shù)之積，且這種分解是唯一的。
- 質(zhì)數(shù)的個數(shù)是無限多的。
- 若n為正整數(shù)，在n2到(n+1)2之間至少有一個質(zhì)數(shù)
- 若n為大于等于2的正整數(shù)，則n到n!之間至少有一個質(zhì)數(shù)
- 若質(zhì)數(shù)p為不超過n(n≥4)的最大質(zhì)數(shù)，則p＞n/2
- 所有大于10的質(zhì)數(shù)中，個位數(shù)只有1，3，7，9
- 在一個大于1的數(shù)a和它的2倍之間（即區(qū)間（a, 2a]中）必存在至少一個素數(shù)。
- 存在任意長度的素數(shù)等差數(shù)列。
?2、有關(guān)素數(shù)的猜想
- 哥德巴赫猜想：是否每個大于2的偶數(shù)都可寫成兩個素數(shù)之和？
- 孿生素數(shù)猜想：孿生素數(shù)就是差為2的素數(shù)對，例如11和13。是否存在無窮多的孿生素數(shù)？
- 斐波那契數(shù)列內(nèi)是否存在無窮多的素數(shù)？
- 是否有無窮多個的梅森素數(shù)？（所謂梅森數(shù)，是指形如2?－1的一類數(shù)，其中指數(shù)p是素數(shù)，常記為Mp。如果梅森數(shù)是素數(shù)，就稱為梅森素數(shù)。）
- 是否存在無窮個形式如X2+1素數(shù)？
?趣味數(shù)學(xué)
?3到881之內(nèi)的孿生素數(shù)
2至54的素數(shù)
?二、素數(shù)的判斷方法
?1、根據(jù)性質(zhì)去判斷
我們都知道素數(shù)的性質(zhì)是除了1和它自身外，不能被其他自然數(shù)整除，所以第一個方法就是從2到n-1一個個去判斷是否有數(shù)可以除以該數(shù)且為0,即 n%i==0；如果有則不是素數(shù)，如果遍歷一遍都沒有數(shù)可以整除它，則就是素數(shù)。
public class Main {
public static boolean isPrime(int n){
if (n <= 3) {
return n > 1;
}
for (int i=2;i<n;i++){
if (n%i==0)
return false;
}
return true;
}
public static void main(String[] args) {
for (int i=2;i<100;i++){//找2到100之間的素數(shù)
if (isPrime(i))
System.out.print(i+" ");
//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
}
}
}?2、改進1方法（縮小比較范圍√n）
看了方法一，大家覺得浪費了很多時間，不必一直循環(huán)到n-1，因為如果a*b=n，則其中必有一個大于sqrt(n)?，一個小于sqrt(n),，所以我們把循環(huán)范圍縮小到√n。
public class Main {
public static boolean isPrime(int n){
if (n <= 3) {
return n > 1;
}
for (int i=2;i<=Math.sqrt(n);i++){
if (n%i==0)
return false;
}
return true;
}
public static void main(String[] args) {
for (int i=2;i<100;i++){//找2到100之間的素數(shù)
if (isPrime(i))
System.out.print(i+" ");
//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
}
}
}3、再次分析素數(shù)的特點，得出規(guī)律
其實素數(shù)還有一個特點，就是它總是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然數(shù)。
這個結(jié)論其實很容易論證。首先 6x 肯定不是質(zhì)數(shù)，因為它能被 6 整除；然后6x+2 肯定也不是質(zhì)數(shù)，因為它還能被2整除；依次類推，6x+3 肯定能被 3 整除；6x+4 肯定能被 2 整除。那么，就只有 6x+1 和 6x+5 (相當(dāng)于6x-1) 可能是質(zhì)數(shù)了。所以循環(huán)的步長可以設(shè)為 6，然后每次只判斷 6 兩側(cè)的數(shù)即可。我們也可以通過孿生素數(shù)可以很清楚的驗證這個規(guī)律。
?這樣我們又可以更加便捷的找出想要找的素數(shù)。
public class Main {
public static boolean isPrime(int num) {
if (num <= 3) {
return num > 1;
}
// 不是在6的倍數(shù)兩側(cè)的一定不是素數(shù)數(shù)
if (num % 6 != 1 && num % 6 != 5) {
return false;
}
//同樣的在6的倍數(shù)兩側(cè)的數(shù)也不一定是素數(shù)，還是要判斷
int sqrt = (int) Math.sqrt(num);
for (int i = 5; i <= sqrt; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
for (int i=2;i<100;i++){//找2到100之間的素數(shù)
if (isPrime(i))
System.out.print(i+" ");
//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
}
}
}問題：枚舉n以內(nèi)所有素數(shù)
上面方法都是用來判斷是不是,但是當(dāng)叫你求n內(nèi)素數(shù)的個數(shù)時，這樣一個個去判斷的時間復(fù)雜度過大，太費時間，這就需要下面的方法了。
?4、埃氏篩法（埃拉托斯特尼篩法）
埃氏篩法就是先把所有整數(shù)列出來，然后把2的倍數(shù)全部剔除，然后是三的，以此類推，遍歷所有素數(shù)，把倍數(shù)全部劃去。對于某個數(shù)字i，如果沒被劃去，他一定是素數(shù)，因為他不是任何2到i-1數(shù)字的倍數(shù)。然后就開始劃它的倍數(shù)就好。
import java.util.Arrays;
public class Main {
static int isPrime(int n)
{
int[] b=new int[n+1];//通過數(shù)組b的值，為1就是素數(shù)
int p=0;//記錄素數(shù)個數(shù)
for(int i=0;i<n+1;i++)
b[i]=1;
b[0]=0;
b[1]=0;
//準(zhǔn)備完畢
for(int i=2;i<=n;i++){
if(b[i]!=0){
p++;//i是素數(shù)即i++;然后剔除i的倍數(shù)
for(int j=2*i;j<=n;j+=i)
b[j]=0;//剔除倍數(shù)
}
}
return p;//返回素數(shù)個數(shù)
}
public static void main(String[] args) {
//找2到100之間的素數(shù)
System.out.print(isPrime(100));//25
//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
}
}或者使用boolean值來進行辨別是否為素數(shù)，我們可以埃氏篩法把所有素數(shù)找出來，然后繼續(xù)O（1）操作來判斷i是否為素數(shù)。
public class Main {
public static void main(String[] args) {
boolean[] isPrime=new boolean[100+1]; //true為素數(shù)
isPrime[0]=false;
isPrime[1]=false;
for (int i=2;i<100+1;i++) isPrime[i]=true;
for (int i=2;i<100+1;i++){
if (isPrime[i]){
for (int j=2;i*j<100+1;j++)
isPrime[i*j]=false;
}
}
}
}?很上面一樣可以進行優(yōu)化不必一直循環(huán)到n，到Math.sqrt(n)就可以。
public class Main {
public static void main(String[] args) {
boolean[] isPrime=new boolean[100+1]; //true為素數(shù)
isPrime[0]=false;
isPrime[1]=false;
for (int i=2;i<100+1;i++) isPrime[i]=true;
for (int i=2;i<Math.sqrt(101);i++){
if (isPrime[i]){
for (int j=2;i*j<100+1;j++)
isPrime[i*j]=false;
}
}
for (int i=2;i<isPrime.length;i++){
if (isPrime[i])
System.out.print(i+" ");
//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
}
}
}5、歐拉篩法（埃氏篩法的優(yōu)化版）
在埃氏篩法中，由于一個數(shù)可以既是一個素數(shù)的倍數(shù)，又是另一個素數(shù)的倍數(shù)，可以發(fā)現(xiàn)這會出現(xiàn)重復(fù)標(biāo)記的情況，即同一個數(shù)被篩掉了不止一次，如果n值過大，則也是一筆不小的時間開銷。
歐拉篩法就是在埃氏算法的基礎(chǔ)上多了判斷的步驟，從而消去了這種重復(fù)標(biāo)記的情況，核心思路是用合數(shù)中的一個因數(shù)篩掉這個合數(shù)。
public static void eulerSieve(int n){
boolean[] isPrime = new boolean[n+1];
int[] Prime=new int[n];//存放素數(shù)的數(shù)組，false為素數(shù)
isPrime[0] = isPrime[1] = true;//數(shù)字0和1都不是素數(shù)，所以賦true
int count = 0;
Prime[count++] = 2;//把2放進素數(shù)表
for (int i = 2; i <n+1; i++) {
if (!isPrime[i])//若當(dāng)前數(shù)是素數(shù)
Prime[count++] = i;//則存入素數(shù)數(shù)組
for (int j = 0; j < count && Prime[j] * i < n+1; j++) {
isPrime[i * Prime[j]] = true;
if (i % Prime[j] == 0)
break;//避免重篩,使得程序更有效率
}
}
}可以看?歐拉篩法尋找10以內(nèi)的素數(shù)，可以發(fā)現(xiàn)完全沒有重復(fù)判斷的數(shù)，因為多了一個判斷，大幅增加了篩素數(shù)的速度，時間復(fù)雜度為O（n）。
文章來源：http://www.zghlxwxcb.cn/news/detail-414318.html
三、素數(shù)相關(guān)題目
藍橋杯之找素數(shù)（填空題+編程題）_冷兮雪的博客-CSDN博客文章來源地址http://www.zghlxwxcb.cn/news/detail-414318.html
到了這里，關(guān)于藍橋杯之素數(shù)及相關(guān)判斷方法（看這一篇就夠了）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
