JS 用6N±1法求素?cái)?shù) 實(shí)例教程
更新時(shí)間：2009年10月20日 15:23:26 作者：
顯然，當(dāng)N≥1時(shí)，6N，6N+2，6N+3，6N+4都不是素?cái)?shù)，只有形如6N+1和6N+5的自然數(shù)有可能是素?cái)?shù)。所以，除了2和3之外，所有的素?cái)?shù)都可以表示成6N±1的形式(N為自然數(shù))。
用6N±1法求素?cái)?shù)
任何一個(gè)自然數(shù)，總可以表示成為如下的形式之一：
6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
顯然，當(dāng)N≥1時(shí)，6N，6N+2，6N+3，6N+4都不是素?cái)?shù)，只有形如6N+1和6N+5的自然數(shù)有可能是素?cái)?shù)。所以，除了2和3之外，所有的素?cái)?shù)都可以表示成6N±1的形式(N為自然數(shù))。
根據(jù)上述分析，我們可以構(gòu)造另一面篩子，只對(duì)形如6 N±1的自然數(shù)進(jìn)行篩選，這樣就可以大大減少篩選的次數(shù)，從而進(jìn)一步提高程序的運(yùn)行效率和速度。
以下代碼需要自然數(shù)大于10
function fn(num){
var arr = [];
arr.push(2);
arr.push(3);
arr.push(5);
arr.push(7);
var t = 0;
for (var i = 3; t < num; i = i + 3) {
for (var j = 0; j < 2; j++) {
t = 2 * (i + j) - 1;
if (t < num && (t % 5 == 0 ? false : t % 7 == 0 ? false : true)) {
arr.push(t);
}
}
}
return arr.join(” “);
}
document.write(fn(1000));
各位大俠有沒有更高效的方法或以上代碼有不對(duì)的地方，請(qǐng)指出。
任何一個(gè)自然數(shù)，總可以表示成為如下的形式之一：
6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
顯然，當(dāng)N≥1時(shí)，6N，6N+2，6N+3，6N+4都不是素?cái)?shù)，只有形如6N+1和6N+5的自然數(shù)有可能是素?cái)?shù)。所以，除了2和3之外，所有的素?cái)?shù)都可以表示成6N±1的形式(N為自然數(shù))。
根據(jù)上述分析，我們可以構(gòu)造另一面篩子，只對(duì)形如6 N±1的自然數(shù)進(jìn)行篩選，這樣就可以大大減少篩選的次數(shù)，從而進(jìn)一步提高程序的運(yùn)行效率和速度。
以下代碼需要自然數(shù)大于10
復(fù)制代碼 代碼如下:
function fn(num){
var arr = [];
arr.push(2);
arr.push(3);
arr.push(5);
arr.push(7);
var t = 0;
for (var i = 3; t < num; i = i + 3) {
for (var j = 0; j < 2; j++) {
t = 2 * (i + j) - 1;
if (t < num && (t % 5 == 0 ? false : t % 7 == 0 ? false : true)) {
arr.push(t);
}
}
}
return arr.join(” “);
}
document.write(fn(1000));
各位大俠有沒有更高效的方法或以上代碼有不對(duì)的地方，請(qǐng)指出。
您可能感興趣的文章:
- 解析利用javascript如何判斷一個(gè)數(shù)為素?cái)?shù)
- JavaScript顯示表單內(nèi)元素?cái)?shù)量的方法
- js獲取json元素?cái)?shù)量的方法
- ASP之處理用Javascript動(dòng)態(tài)添加的表單元素?cái)?shù)據(jù)的代碼
- javascript實(shí)現(xiàn)計(jì)算指定范圍內(nèi)的質(zhì)數(shù)示例
- javascript實(shí)現(xiàn)Emrips反質(zhì)數(shù)枚舉的示例代碼
- JavaScript判斷數(shù)字是否為質(zhì)數(shù)的方法匯總
- JavaScript實(shí)現(xiàn)找質(zhì)數(shù)代碼分享
- JS實(shí)現(xiàn)判斷有效的數(shù)獨(dú)算法示例
- JS實(shí)現(xiàn)計(jì)算小于非負(fù)數(shù)n的素?cái)?shù)的數(shù)量算法示例
相關(guān)文章
這篇文章主要介紹了js處理跨域的方案之jsonp用法的相關(guān)資料,文中分享了前端調(diào)用后端接口的三種方式：Ajax、fetch、axios,并詳細(xì)解釋了同源策略和跨域的概念,需要的朋友可以參考下2024-11-11
本篇文章主要是對(duì)JS保留兩位小數(shù),多位小數(shù)的示例代碼進(jìn)行了介紹，需要的朋友可以過來參考下，希望對(duì)大家有所幫助2014-01-01
clearInterval()方法能夠取消setInterval()方法設(shè)置的定時(shí)器，本文給大家詳解clearInterval()方法的定義和用法，感興趣的朋友參考下。2015-11-11
bootstrap table插件動(dòng)態(tài)加載表頭
這篇文章主要為大家詳細(xì)介紹了bootstrap table插件動(dòng)態(tài)加載表頭，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-07-07
這篇文章主要介紹了前端解決滾動(dòng)穿透問題的五種常見方法,并詳細(xì)分析了它們的優(yōu)缺點(diǎn)和適用場景,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2025-03-03
iframe src為圖片時(shí)的高度自適應(yīng)的代碼
iframe src為圖片時(shí)的高度自適應(yīng)的代碼...2007-10-10
javascript數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹實(shí)現(xiàn)方法
這篇文章主要介紹了javascript數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹實(shí)現(xiàn)方法,較為詳細(xì)的分析了二叉搜索樹的概念、原理與JavaScript實(shí)現(xiàn)二叉搜索樹的方法,對(duì)于學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-11-11
最近因?yàn)楣ぷ餍枰钊氲膶W(xué)習(xí)JavaScript，發(fā)現(xiàn)如果囫圇吞棗印象就是不深刻，自己去練習(xí)一下才能慢慢有點(diǎn)感覺。本文主要是詳解堆的javascript實(shí)現(xiàn)方法，另外堆排序?qū)ξ覀儊碚f太耳熟而又少用的情況下，本文當(dāng)作一次復(fù)習(xí)。感興趣的朋友們下面來一起看看吧。2016-11-11
本篇文章主要是對(duì)js根據(jù)日期判斷星座的示例代碼進(jìn)行了介紹，需要的朋友可以過來參考下，希望對(duì)大家有所幫助2014-01-01
ES6中Array.includes()函數(shù)的用法
這篇文章主要介紹了ES6中Array.includes()函數(shù)的用法,需要的朋友可以參考下2017-09-09