當前位置:編程學習大全網 - 編程軟體 - 用C語言編程求:n以內素數的個數(n<10^8)

用C語言編程求:n以內素數的個數(n<10^8)

首先肯定要定義成long 型了

這個n 從以下幾方面進行處理:

1:偶數者除了2以外均不是,任務將縮短壹半 可采用 n+=2實現

2:最後壹位是5的除了5以外不是素數,任務在1的基礎上縮短1/5

3:在判斷能被3及根號或壹半n之間的數據時,也采用全用質數的方法i+=2 以及除去尾數是5的數。這樣在每個n值下,檢測不能被i整除的任務將縮短1/2+1/5即7/10。

4:對於數據較大的n可以采用位運算、移位運算、加法運算將其十進制時各位數字之和除以3,能整除者不是素數。

建議采用三級處理1-10 10-100 000 100 000-100000000分別編制程序段采用不同方法實現。

1-10 :簡單處理

1 0-100 000:采用1,2,3(i采用3——n/2)

100 000-100000000:采用1,2,3(i采用3——根號n),4

“warmwormn - 舉人 五級

。。。。。。。

篩選

每次把質數的倍數全部刪除

只有循環和加法

綜觀不如樓上的方法(但實現很麻煩,並且表達不對):如下

1定義壹個素數存儲數組a:

2每壹個n(>2),除去偶數,只要將已經存在在a中數據進行組合相乘,均不與當前n相等的話,則n 為素數,存入a 中

3當然在組合過程中,

!: 明顯小於前壹個n時,可舍去不再比較,也不再累計到下壹個n的比較。

!!:大於當前n及其後面的組合可舍去不再比較,但需要累計到下壹個n的比較。

只有利用了這種方法,才有可能,降低運算工作量

  • 上一篇:聖誕樹圖形有幾個角
  • 下一篇:寧波市奉化弘博自動化科技有限公司怎麽樣?
  • copyright 2024編程學習大全網