|
何謂素?cái)?shù)? 數(shù)學(xué)家們說 所謂素?cái)?shù)就是因數(shù)除了1就是他們本身的自然數(shù)。 它們就是數(shù)學(xué)世界的顏值擔(dān)當(dāng) 自從歐（幾里德）先生證明說 它的伙伴有無窮多后 無數(shù)數(shù)學(xué)家開始為之傾倒 有許多默默無聞的數(shù)學(xué)家 一直在不斷地研究著這些高顏值數(shù)字 感興趣的同學(xué) 可以翻看以下內(nèi)容： http://www./cms/sxxw/20130529.htm IT、數(shù)學(xué)不分家 數(shù)學(xué)家感興趣的內(nèi)容 ITer也不能輕易放過 最近就有一個同學(xué) 迷上了她 “如何將100到200之間的素?cái)?shù)很快地計(jì)算并輸出？” 同學(xué)用JAVA實(shí)現(xiàn)如下 public static void main(String[] args) { for(int i=100; i<201;> boolean b=true; for(int j=2; j if(i%j==0){ b=false; } } if(b==true){ System.out.println(i); } } } 運(yùn)行結(jié)果整齊如下 從結(jié)果來看 如果沒數(shù)錯的話 100-200之間 共有21個素?cái)?shù) 同學(xué)說 這個問題的解決方案不太滿意 這些代碼要繼續(xù)優(yōu)化 但是遺憾的是 不知道從哪里開始 從算法的角度來看 是否最優(yōu) 有兩個維度 一是時間復(fù)雜度 另外一個就是空間復(fù)雜度 那么就從這里開始吧~ 于是 帶著最初的夢想 邁著蹣跚的步伐 開始改進(jìn) 第1版： 從時間的角度來看 節(jié)省若干次循環(huán)開銷 public static void main(String[] args) { for(int i=100; i<201;> boolean b=true; for(int j=2; j; j++){ if(i%j==0){ b=false; } } if(b==true){ System.out.println(i); } } } 假設(shè)執(zhí)行一次循環(huán)需要1個時間單位 那么這個改進(jìn)會節(jié)省多少時間呢? 這個復(fù)雜的數(shù)學(xué)問題 就留給數(shù)學(xué)系的天才們吧 ITer們只銷曉得 邁出這樣一小步 節(jié)約開銷一大步 就好~ 這樣看來 節(jié)約時間還可以有其他版本啦~ 比如說 不要再執(zhí)行到i/2 截止到i的平方根就好 可以不 有無數(shù)數(shù)學(xué)家說這樣做是沒問題的~ 程序也證明了這一點(diǎn) 于是就出現(xiàn)了 第2版： public static void main(String[] args) { for(int i=100; i<201;> boolean b=true; for(int j=2; j<>; j++){ if(i%j==0){ b=false; } } if(b==true){ System.out.println(i); } } } 各位要特別注意 在循環(huán)條件處要加上“=” 否則的話 121和169之類的數(shù)字就要粉墨登場了~ 可還有別的思路 能不能再節(jié)約點(diǎn)其他開銷？ 試著思考以下問題：
當(dāng)把這些問題想清楚后 又一個方案浮出水面 第3版： public static void main(String[] args) { int j; for(int i=100; i<201;> for(j=2; j<>; j++){ if(i%j==0){ break; } } if(j>(Math.sqrt(i))){ System.out.println(i); } } } Did you get it? If so 恭喜你 If no 回復(fù)我 如果您也誨人不煩 耐心看到了這里 那就再接受一個不情之請 動動小手指 把小文轉(zhuǎn)發(fā)到你的圈中 不一定在哪里 就會有位需要的人 幫人一忙 勝造N級浮屠 |
|
|
