2007年2月18日

求1億以下的質數

public ? class ?Prime? {

???? public ? static ? void ?main(String[]?args)? {

???????? long ?timeStart? = ?System.currentTimeMillis();

???????? int []?prime_array? = ? new ? int [ 10000 ]; // 用來保存10萬以下的質數(共9592個)

????????prime_array[ 0 ] = 3 ;

????????prime_array[ 1 ] = 5 ;

???????? int ?i,primeId =- 1 ,m = 2 ,prime;

???????? // System.out.println(2); // 質數2直接打出^_^

???????? for ?( int ?a? = ? 3 ;?a? <= ? 100000 ;?a? += ? 2 )? {

???????????? if (m * m < a) {

???????????????? // 避免使用sqrt()

????????????????m ++ ;

????????????}

???????????? for ?(i = 0 ;(prime = prime_array[i]) <= m;i ++ )? {

???????????????? if ?(a? % ?prime? == ? 0 )? {

???????????????????? break ;

????????????????}

????????????}

???????????? if ?(prime > m)? {

????????????????prime_array[ ++ primeId] = a;

???????????????? // 10萬以下的質數存起

???????????????? // System.out.print(a+"?");

????????????}

????????}

????????System.out.println( " 計算10萬以下的質數(共 " + (primeId + 2 ) + " 個)耗時 " + (System.currentTimeMillis() - timeStart) + " 毫秒. " );

???????? int ?maxNum = 100000000 ;

???????? for ( int ?a? = ? 100001 ;?a? <= ?maxNum;?a? += ? 2 ) {

???????????? if (m * m < a) {

???????????????? // 避免使用sqrt()

????????????????m ++ ;

????????????}

???????????? for ?(i = 0 ;(prime = prime_array[i]) <= m;i ++ )? {

???????????????? if ?(a? % ?prime? == ? 0 )? {

???????????????????? break ;

????????????????}

????????????}

???????????? if ?(prime > m)? {

???????????????? ++ primeId;

???????????????? // System.out.print(a+"?");

????????????}

????????}

????????System.out.println(maxNum + " 以下共 " + (primeId + 2 ) + " 個質數. " );

????????System.out.println( " 耗時 " + (System.currentTimeMillis() - timeStart) + " 毫秒. " );

????}

}

posted @ 2007-02-18 21:20 zero 閱讀(425) | 評論 (1) | 編輯收藏

HelloWorld~

今天開始看java,我寫的第一個東東~

public?class?HelloWorld?{
2

????public?static?void?main(String[]?args)?{
3

????????System.out.println("Hello?World!");
4

????}
5

}
6

posted @ 2007-02-18 21:17 zero 閱讀(130) | 評論 (1) | 編輯收藏

導航

統計

常用鏈接

留言簿(1)

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

2007年2月18日