今天咱們來(lái)點(diǎn)不一樣的，來(lái)看一下這樣的一道題目，他要求我們把1-1000的素?cái)?shù)全部找到并且輸出

那我們先要了解什么是素?cái)?shù)，所謂素?cái)?shù)，就是指在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)的自然數(shù)。而合數(shù)則恰巧與素?cái)?shù)相反，是指在大于1的整數(shù)中除了能被1和本身整除外，還能被其他數(shù)（0除外）整除的數(shù)

解法一

那我們根據(jù)定義解法一就得出來(lái)了，那就是從2開(kāi)始到1000進(jìn)行遍歷，然后一個(gè)一個(gè)確認(rèn)它除了1和它本身還有沒(méi)有其他的因子，然后大家都知道2是最小的素?cái)?shù)，而2以外的正偶數(shù)都是合數(shù)，所以咱們可以對(duì)它進(jìn)行一些小的改進(jìn)和優(yōu)化??

#include <iostream>
#include <iomanip>? ? //setw()對(duì)應(yīng)的頭文件
using namespace std;
int main () 
{
    int n,i;
    bool k= false ;? ? //設(shè)置布爾類(lèi)型的變量以方便進(jìn)行對(duì)素?cái)?shù)的標(biāo)記
    cout << setw(5) << 2 ;? ? //2是最小的素?cái)?shù)
    for(n=3;n<1001;n+=2){
        k=true;
        for(i=2;i<n;i++){
            if(n%i==0){
            k= false ;
            break;    ? //是合數(shù)就跳出循環(huán)
            }
        }
        if(k){     //由標(biāo)記決定是否為素?cái)?shù)
            cout << setw(5) << n ;? ? //輸出進(jìn)行格式化，以便查看
        }
    }
    return 0;
}

通過(guò)這個(gè)方法是可以做出這道題目的，但是放在洛谷或者學(xué)校的oj網(wǎng)站上卻老是WA，這又是為什么呢，其實(shí)是我們的程序運(yùn)行太過(guò)復(fù)雜，它的時(shí)間復(fù)雜度為O(n)，這是很容易使整個(gè)程序崩潰的，所以我們一定要學(xué)會(huì)對(duì)自己的算法進(jìn)行優(yōu)化，降低它的時(shí)間復(fù)雜度和空間復(fù)雜度

優(yōu)化如下??

解法一優(yōu)化

#include <iostream>
#include <iomanip>
using namespace std;
int main () 
{
    int n,i;
    bool k= false ;
    cout << setw(5) << 2 ;
    for(n=3;n<1001;n+=2){
        k=true;
        for(i=2;i<=n/i;i++){       //將i的范圍大大縮小
            if(n%i==0){
            k= false ;
            break;    
            }
        }
        if(k){
            cout << setw(5) << n ;
        }
    }
    return 0;
}

這樣我們的程序就能運(yùn)行出來(lái)了，根本就在于我將他的檢測(cè)范圍由原來(lái)的n變成了sqrt(n)，也就是n的開(kāi)方，那它的時(shí)間復(fù)雜度自然也從O(n)---變成了---->O(sqrt(n))

以上是我們的解法一，接下來(lái)介紹一種素?cái)?shù)篩查法

解法二

所謂素?cái)?shù)篩查法，顧名思義就是要通過(guò)篩掉合數(shù)的方法來(lái)找出素?cái)?shù)。

這里有一個(gè)定理要介紹給大家：一個(gè)合數(shù)一定能夠?qū)懗扇舾蓚€(gè)素?cái)?shù)之積的形式。那么我們就只需要把2的倍數(shù)找出來(lái)扔掉，3的倍數(shù)找出來(lái)扔掉，5的倍數(shù)找出來(lái)扔掉，7的倍數(shù)找出來(lái)扔掉，11的倍數(shù)找出來(lái)扔掉……以此類(lèi)推，直到這個(gè)素?cái)?shù)是小于等于n開(kāi)方的最大素?cái)?shù)就OK了

然后思路明白了，大家拿代碼實(shí)現(xiàn)就好了。首先要扔掉那就要先存起來(lái)，那就要用到數(shù)組這個(gè)東西，這樣的話我們只需要將合數(shù)變成0，素?cái)?shù)留下，最后遍歷數(shù)組的時(shí)候判斷一下就OK了。

但是值得大家注意的一點(diǎn)是：這幾個(gè)素?cái)?shù)因子也會(huì)被判斷為合數(shù)，故此我們要提前輸出這幾個(gè)素?cái)?shù)因子以保證它的完整性

#include <iostream>
#include <iomanip> 
using namespace std;
int main()
{
    int a[1001]={0};
    int i;
    cout << setw(5) << 2 << setw(5) << 3 << setw(5) << 5 << setw(5) << 7 ;
? ? cout << setw(5) << 11 << setw(5) << 13 << setw(5) << 17<< setw(5) << 19 ;
? ? cout << setw(5) << 23 << setw(5) << 29 << setw(5) << 31 ;     
                             //這是在保證完整性！?。。ǚ挪幌戮蛯?xiě)下一行了）
    for(i=3;i<1001;i++){
        if(i%2!=0&&i%3!=0&&i%5!=0&&i%7!=0&&i%11!=0&&i%13!=0&&i%17!=0&&i%19!=0&&i%23!=0&&i%29!=0&&i%31!=0)
        a[i]=i;? ? ? ? //是質(zhì)數(shù)才輸入，否則就是初始化的0
    }
    for(i=0;i<1001;i++){
        if(a[i]!=0)? ? ? ? //判斷是否為素?cái)?shù)
        cout << setw(5) << a[i] ;
    }
    return 0;
}

對(duì)于這個(gè)解法的優(yōu)化方法，我們還要用到另一個(gè)定理——從5開(kāi)始，素?cái)?shù)一定在6的倍數(shù)周?chē)ㄖ槐人?或小1），有了這個(gè)定理，那我們的數(shù)據(jù)范圍就會(huì)變得更小，改進(jìn)如下??

解法二優(yōu)化

#include <iostream>
using namespace std;
#include <iomanip>
int isPrime (int a);? ? ? ? //聲明一個(gè)新的函數(shù)來(lái)判斷是否為素?cái)?shù)
int main()
{
    int a,b,i;
    cout << setw(5) << 2 << setw(5) << 3 << setw(5) << 5 << setw(5) << 7 ;
    cout << setw(5) << 11 << setw(5) << 13 << setw(5) << 17<< setw(5) << 19 ;
    cout << setw(5) << 23 << setw(5) << 29 << setw(5) << 31 ;  
    for(i=6;i<167;i++){
        a=6*i-1;
        b=6*i+1;
        if(isPrime (a))
        cout << setw(5) << isPrime (a) ;? ? ? ? //返回了非零數(shù)字就輸出
        if(isPrime (b))
        cout << setw(5) << isPrime (b) ;? ? ? ? //返回了非零數(shù)字就輸出
    }
    return 0;
}
int isPrime (int a)
{
    if(a%2!=0&&a%3!=0&&a%5!=0&&a%7!=0&&a%11!=0&&a%13!=0&&a%17!=0&&a%19!=0&&a%23!=0&&a%29!=0&&a%31!=0)
    return a ;? ? ? ? ? ? //如果為素?cái)?shù)返回此數(shù)
    else 
    return false ;? ? ? ? //如果為合數(shù)終止程序
}

這就是查找素?cái)?shù)的方法，還有一種運(yùn)用費(fèi)馬小定理的解法，那個(gè)方法只能保證找到的數(shù)字大概率是素?cái)?shù)，不能夠百分百的保證，所以暫時(shí)先不給大家介紹誤導(dǎo)大家了。希望以上的解法對(duì)大家有所幫助，謝謝大家的閱讀~~~文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-457459.html