tft每日頭條

 > 圖文

 > c語言中判斷質數的算法

c語言中判斷質數的算法

圖文 更新时间:2024-08-14 01:16:14

c語言中判斷質數的算法(C語言經典算法篩選法求質數)1

小編是一個有着6年工作經驗的工程師,關于C 編程,自己有做材料的整合,一個完整的C 編程學習路線,學習資料和工具,能夠進我的群10048,-83029收取,免費送給大家,希望你也能憑着自己的努力,成為下一個優秀的程序員

c語言中判斷質數的算法(C語言經典算法篩選法求質數)2

明除了自身之外,無法被其它整數整除的數稱之為質數,要求質數很簡單,但如何快速的求出質數則一直是程式設計人員與數學家努力的課題,在這邊介紹一個着名的 Eratosthenes求質數方法。

c語言中判斷質數的算法(C語言經典算法篩選法求質數)3

首先知道這個問題可以使用回圈來求解,将一個指定的數除以所有小于它的數,若可以整除就不是質數,然而如何減少回圈的檢查次數?

如何求出小于N的所有質數?

首先假設要檢查的數是N好了,則事實上隻要檢查至N的開根号就可以了,道理很簡單。

假設A*B = N,如果A大于N的開根号,則事實上在小于A之前的檢查就可以先檢查到B這個數可以整除N。

不過在程式中使用開根号會精确度的問題,所以可以使用 i*i <= N進行檢查,且執行更快。

再來假設有一個篩子存放1~N,例如:

23 456789101112131415161718192021 ....N

先将2的倍數篩去:

23 579111315171921....N

再将3的倍數篩去:

23 5711131719....N

再來将5的倍數篩去,再來将7的質數篩去,再來将11的倍數篩去........,如此進行到最後留下的數就都是質數,這就是Eratosthenes篩選方法(Eratosthenes Sieve Method)。

檢查的次數還可以再減少,事實上,隻要檢查6n 1與6n 5就可以了,也就是直接跳過2與3的倍數,使得程式中的if的檢查動作可以減少

c語言中判斷質數的算法(C語言經典算法篩選法求質數)4

這個算法,你懂了嗎?

,

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

查看全部

相关圖文资讯推荐

热门圖文资讯推荐

网友关注

Copyright 2023-2024 - www.tftnews.com All Rights Reserved