何謂素?cái)?shù)?

數(shù)學(xué)家們說(shuō)

所謂素?cái)?shù)就是因數(shù)除了1就是他們本身的自然數(shù)。

它們就是數(shù)學(xué)世界的顏值擔(dān)當(dāng)

自從歐（幾里德）先生證明說(shuō)

它的伙伴有無(wú)窮多后

無(wú)數(shù)數(shù)學(xué)家開始為之傾倒

有許多默默無(wú)聞的數(shù)學(xué)家

一直在不斷地研究著這些高顏值數(shù)字

感興趣的同學(xué)

可以翻看以下內(nèi)容：

http://www./cms/sxxw/20130529.htm

IT、數(shù)學(xué)不分家

數(shù)學(xué)家感興趣的內(nèi)容

ITer也不能輕易放過(guò)

最近就有一個(gè)同學(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é)果來(lái)看

如果沒(méi)數(shù)錯(cuò)的話

100-200之間

共有21個(gè)素?cái)?shù)

同學(xué)說(shuō)

這個(gè)問(wèn)題的解決方案不太滿意

這些代碼要繼續(xù)優(yōu)化

但是遺憾的是

不知道從哪里開始

從算法的角度來(lái)看

是否最優(yōu)

有兩個(gè)維度

一是時(shí)間復(fù)雜度

另外一個(gè)就是空間復(fù)雜度

那么就從這里開始吧~

于是

帶著最初的夢(mèng)想

邁著蹣跚的步伐

開始改進(jìn)

第1版：

從時(shí)間的角度來(lái)看

節(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個(gè)時(shí)間單位

那么這個(gè)改進(jìn)會(huì)節(jié)省多少時(shí)間呢?

這個(gè)復(fù)雜的數(shù)學(xué)問(wèn)題

就留給數(shù)學(xué)系的天才們吧

ITer們只銷曉得

邁出這樣一小步

節(jié)約開銷一大步

就好~

這樣看來(lái)

節(jié)約時(shí)間還可以有其他版本啦~

比如說(shuō)

不要再執(zhí)行到i/2

截止到i的平方根就好

可以不

有無(wú)數(shù)數(shù)學(xué)家說(shuō)這樣做是沒(méi)問(wèn)題的~

程序也證明了這一點(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ù)字就要粉墨登場(chǎng)了~

可還有別的思路

能不能再節(jié)約點(diǎn)其他開銷？

試著思考以下問(wèn)題：

1. 每次內(nèi)循環(huán)中，新建一個(gè)boolean變量是必要的嗎？

2. 如果內(nèi)循環(huán)中已經(jīng)出現(xiàn)了i%j值為0的情況，內(nèi)循環(huán)還有必要執(zhí)行嗎？

當(dāng)把這些問(wèn)題想清楚后

又一個(gè)方案浮出水面

第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ù)我

如果您也誨人不煩

耐心看到了這里

那就再接受一個(gè)不情之請(qǐng)

動(dòng)動(dòng)小手指

把小文轉(zhuǎn)發(fā)到你的圈中

不一定在哪里

就會(huì)有位需要的人

幫人一忙

勝造N級(jí)浮屠