/** * 题目名称第n小的质数 p * 题目来源http://noi.openjudge.cn/ch0105/44/ p * 程序功能输出指定编号的质数 * * author 潘磊just_panleijust.edu.cn * version 1.0 */importjava.util.Scanner;publicclassMain{/** * 判断指定正整数是否为质数。 * * param num 指定正整数。 * return true当且仅当num是质数否则false。 */publicbooleanisPrime(intnum){if(num2){// 小于2的整数不是质数returnfalse;}if(num2){// 2是质数returntrue;}if(num%20){// 除2以外其它偶数都不是质数returnfalse;}/* 从3依次遍历到sqrt(num)仅遍历奇数 */for(inti3;i*inum;i2){if(num%i0){// 如果当前整数是num的因子returnfalse;// 说明num不是质数}}returntrue;// 以上没有返回false说明num是质数}/** * 返回指定编号的质数。 * * param n 指定编号。 * return 第n个质数。 */publicinttheNthPrime(intn){if(n1){// 第一个质数是2return2;}n--;// 去掉质数2查找的质数数量减1intans-1;// 第n个质数初始为-1这里初始值可以是任意整数/* 从3开始依次遍历每个奇数直至找到第n个质数 */for(inti3;n0;i2){if(isPrime(i)){// 如果当前整数是质数ansi;// 更新ans为当前整数n--;// 令查找的质数数量减1}}returnans;}publicstaticvoidmain(String[]args){MaincallnewMain();ScannerinputnewScanner(System.in);intninput.nextInt();System.out.print(call.theNthPrime(n));}}
/** * 题目名称第n小的质数 p * 题目来源http://noi.openjudge.cn/ch0105/44/ p * 程序功能输出指定编号的质数 * * author 潘磊just_panleijust.edu.cn * version 1.0 */importjava.util.Scanner;publicclassMain{/** * 判断指定正整数是否为质数。 * * param num 指定正整数。 * return true当且仅当num是质数否则false。 */publicbooleanisPrime(intnum){if(num2){// 小于2的整数不是质数returnfalse;}if(num2){// 2是质数returntrue;}if(num%20){// 除2以外其它偶数都不是质数returnfalse;}/* 从3依次遍历到sqrt(num)仅遍历奇数 */for(inti3;i*inum;i2){if(num%i0){// 如果当前整数是num的因子returnfalse;// 说明num不是质数}}returntrue;// 以上没有返回false说明num是质数}/** * 返回指定编号的质数。 * * param n 指定编号。 * return 第n个质数。 */publicinttheNthPrime(intn){if(n1){// 第一个质数是2return2;}n--;// 去掉质数2查找的质数数量减1intans-1;// 第n个质数初始为-1这里初始值可以是任意整数/* 从3开始依次遍历每个奇数直至找到第n个质数 */for(inti3;n0;i2){if(isPrime(i)){// 如果当前整数是质数ansi;// 更新ans为当前整数n--;// 令查找的质数数量减1}}returnans;}publicstaticvoidmain(String[]args){MaincallnewMain();ScannerinputnewScanner(System.in);intninput.nextInt();System.out.print(call.theNthPrime(n));}}
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
