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) + " 毫秒. " );
????}
}