public ? class ?Prime? {
???? public ? static ? void ?main(String[]?args)? {
???????? long ?timeStart? = ?System.currentTimeMillis();
???????? int []?prime_array? = ? new ? int [ 10000 ]; // 用來(lái)保存10萬(wàn)以下的質(zhì)數(shù)(共9592個(gè))
????????prime_array[ 0 ] = 3 ;
????????prime_array[ 1 ] = 5 ;
???????? int ?i,primeId =- 1 ,m = 2 ,prime;
???????? // System.out.println(2); // 質(zhì)數(shù)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萬(wàn)以下的質(zhì)數(shù)存起
???????????????? // System.out.print(a+"?");
????????????}
????????}
????????System.out.println( " 計(jì)算10萬(wàn)以下的質(zhì)數(shù)(共 " + (primeId + 2 ) + " 個(gè))耗時(shí) " + (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 ) + " 個(gè)質(zhì)數(shù). " );
????????System.out.println( " 耗時(shí) " + (System.currentTimeMillis() - timeStart) + " 毫秒. " );
????}
}