aiaiask.com©

开花即结果 提问即答案

输入一个素数,请输出他的原根个数,用JS来实现
原始问题:

输入一个素数,请输出他的原根个数,用JS来实现

要计算一个素数的原根个数,可以使用欧拉函数的性质。欧拉函数(Euler's totient function)表示小于等于n且与n互质的正整数的个数,记为φ(n)。

对于一个素数p,它的原根个数可以通过计算φ(p-1)来得到。

以下是使用JavaScript实现计算素数的原根个数的代码:

function gcd(a, b) {
  if (b === 0) {
    return a;
  }
  return gcd(b, a % b);
}

function eulerTotient(n) {
  let count = 0;
  for (let i = 1; i < n; i++) {
    if (gcd(n, i) === 1) {
      count++;
    }
  }
  return count;
}

function countPrimitiveRoots(p) {
  if (p <= 1 || !Number.isInteger(p) || !isPrime(p)) {
    return -1; // 输入不是素数,返回-1表示错误
  }
  return eulerTotient(p - 1);
}

function isPrime(n) {
  if (n <= 1) {
    return false;
  }
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

// 示例用法
const primeNumber = 13;
const primitiveRootsCount = countPrimitiveRoots(primeNumber);
console.log(`素数 ${primeNumber} 的原根个数为 ${primitiveRootsCount}`);

请注意,以上代码中的 isPrime 函数用于判断一个数是否为素数。在实际应用中,可以使用更高效的素数判定算法来替代。

希望以上代码能够满足你的需求。如果有任何问题,请随时提问。

输入一个素数,请输出他的原根个数,用JS来实现
https://www.aiaiask.com/ask/45105.html
AI / 模型Siliconflow
时间 / DATEAugust 23, 2023, 9:18 PM
语言zh-CN
IP / 区域湖北 武汉