这是一个创建于 1812 天前的主题，其中的信息可能已经有所发展或是发生改变。
/** * @method getNPower2plus1 求前 m 个满足 n^2+1 的素数 * @return {Array<Number>} pList **/ let getNPower2plus1 = (m) => { let pList = []; let pListLen = 0; // 循环次数 let loopTimes = 0; // n 从 2 开始 let n = 2; // 当 pList 数量小于 m 时，求素数 while (pListLen < m) { loopTimes += 1; let nPow2Plus1 = Math.pow(n, 2) + 1; // 是否为素数 if (isPrimeNumber(nPow2Plus1)) { pList.push(nPow2Plus1); pListLen += 1; } n += 1; } console.log(loopTimes); // 23 return pList; } console.log(getNPower2plus1(8)); // [5,17,37,101,197,257,401,577] 求求好心的大哥大姐帮我解答一下
我疑惑的是 我输入了 8 循环了 20 多次，那么算 logn 吗？
 | 1 zxCoder 2021 年 5 月 8 日 你这算法复杂度不是 O(m*isPrimeNumber 的复杂度)吗？ 而且算法复杂度和循环次数没有关系。。。。。 |
 | 2 geelaw 2021 年 5 月 8 日 via iPhone 答案是暂时不知道，因为这需要探究 n^2+1 里质数的分布 https://math.stackexchange.com/questions/44126/primes-of-the-form-n21-hard 另外任何有限的尝试都不能说明算法的渐近时间复杂度。 |
 | 3 a62527776a OP |
Select Language