問：1-100之間有多少個素數，并輸出所有素數及素數的個數。

這個題面就很容易理解了，數學上對素數的定義是這樣的：質數又稱素數，指在一個大于1的自然數中，除了1和此整數自身外，沒法被其他自然數整除的數。

換句話說，隻有兩個正因數（1和自己）的自然數即為素數。比1大但不是素數的數稱為合數。并且1和0既非素數也非合數。

好了，數學上素數是這樣定義，我們應該把它用計算機的語言表示出來呀。

這裡我們就用一種最簡單的方式來表示：

編程思想：

一個數n，要判斷它是不是素數，直接用n除以2到n裡面所有的數，如果有一個能整除，則這個數n不是素數。如果都不能被整除，則這個數是素數。

上面這句話用代碼寫出來是這樣的：

1. for(j = 2; j<= n; j ) //能被2到n整除的數

2. {

3. if(i % j == 0) //取餘判斷

4. {

5. flag = 0;

6. break;

7. //隻要有一個被整除，則跳出循環

8. }

9. }

到這裡，我們仔細想想，有必要一直除到n去嗎？答案是沒有必要的，來看一個例子。

比如判斷17是不是素數，我們其實隻需要計算：

17%2

17%3

17%4

隻需要計算以上三個式子，我們就可以斷定，17是一個素數。

為什麼呢？因為數學知識告訴我們：任何一個數都不可能分解成兩個大于其平方根的數的乘積呀，肯定隻能分解為一個大于或等于其平方根，另一個小于或等于其平方根的兩個數相乘。

我們知道，17開根号的值是一個4到5之間的數，取int之後就是4，既然我們已經從2一直取餘取到了4都沒有一個可以整除，那麼就沒有必要繼續計算下去了，因為接下來的數也肯定不能被整除。

我們吧代碼優化一下：

1. for(j = 2; j<= sqrt(n); j ) //能被2到n的開方根整除的數

2. {

3. if(i % j == 0)

4. {

5. flag = 0;

6. break;

7. }

8. }

好了，這樣子你能明顯感受到我們一下子減少了很多計算量，時間複雜度降低了。

完整代碼

以上是知道一個數，判斷它是不是素數，這裡我們要做的是輸出1-100内所有的素數，那麼就要有一個雙重for循環，一個數一個數地去判斷，然後輸出素數。

這裡給出完整代碼：

1. //輸出1-100的所有素數

2. void Prime()

3. {

4. int i,j,flag,n;

5. n = 100; //100以内的素數

6. flag = 1; //标識變量，是素數則為1

7. for(i = 2; i <= 100; i ) //從2開始，遍曆到100

8. {

9. flag = 1;

10. for(j = 2; j*j <= i; j ) //能被2 - sqrt(i)整除的數

11. {

12. if(i % j == 0)

13. {

14. flag = 0;

15. break;

16. }

17. }

18. if(flag == 1)

19. printf("%d ",i); //輸出素數

20. }

21. }

與素數有關的猜想

關于求素數，上面的方法是一個最最直接的方法，初學者知道這種方法就可以了。

但其實還有很多比這種方法時間複雜度更低的方法，如果想更進一步探索程序的簡潔和美妙，我明天會整理發出來給大家參考一下。

這裡分享幾個很有意思的猜想：

哥德巴赫猜想

哥德巴赫猜想（Goldbach Conjecture）大緻可以分為兩個猜想（前者稱“強”或“二重哥德巴赫猜想”後者稱“弱”或“三重哥德巴赫猜想”)：1、每個不小于6的偶數都可以表示為兩個奇素數之和；2、每個不小于9的奇數都可以表示為三個奇質數之和。

黎曼猜想

黎曼猜想是一個困擾數學界多年的難題，最早由德國數學家波恩哈德·黎曼提出，迄今為止仍未有人給出一個令人完全信服的合理證明。即如何證明“關于質數的方程的所有意義的解都在一條直線上”。

此條質數之規律内的質數月經過整形，“關于質數的方程的所有意義的解都在一條直線上”化為球體質數分布。

孿生質數猜想

1849年，波林那克提出孿生質數猜想（the conjecture of twin primes），即猜測存在無窮多對孿生質數。

猜想中的“孿生質數”是指一對質數，它們之間相差2。例如3和5，5和7，11和13，10016957和10016959等等都是孿生質數。

10016957和10016959是發生在第333899位序号質數月的中旬[18±1]的孿生質數。

質數月定位孿生質數發生位置：

首個質數月孿生質數發生位置：[T-1]*30 【[4±1] [6±1] [12±1] [18±1] [30±1] 】 T=1

其餘質數月孿生質數發生位置：[T-1]*30 【[0±1] [12±1] [18±1] [30±1] 】 T=N是自然數代表質數月

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部