计算C ++中质数因子的GCD等于1的范围内的数字

给定两个数字，开始和结束分别代表一个正整数范围。目标是找到位于[start，end]范围内并具有素数分解的所有数字的计数，以使该数量的所有素数具有幂，使得它们的GCD为1。

如果一个数的质数分解为2 ^p  * 3 ^q * 5 ^r …..则幂p，q，r ...应具有gcd = 1。

让我们通过示例来理解。

例如

输入-开始= 1，结束= 10 

输出-质数幂的GCD等于1的范围内的数量计数是：6

说明-这些数字是：

2（2 ¹），3（3 ¹），5（5 ¹），7（7 ¹），8（2 ³）和10（2 ¹ * 5 ¹）。每个素数分解的所有幂的gcd为1。

输入-开始= 11，结束= 20 

输出-质数幂的GCD等于1的范围内的数量计数是：9

说明-这些数字是：

11（11 ¹），12（3 ¹ * 2 ²），13（13 ¹），14（2 ¹ * 7 ¹），15（3 ¹ * 5 ¹），17（17 ¹），18（2 ¹ * 3 ²），19（19 ¹ ）和20（2 ² * 5 ¹）。每个素数分解的所有幂的gcd为1。

以下程序中使用的方法如下

在这种方法中，我们将计算从开始到结束范围内不是完美功效的所有数字。由于非完美的功率将满足上述条件。为此，我们将找到所有完美的力量，并将其从总数中删除。 

答案将是=开始-结束+1-（范围[start，end]内的完美幂的数量的计数）。

• 将范围变量start和end作为输入。

• 取向量vec来存储大于3的幂。

• 进行设定以存储为完美平方的数字。

• 进行sett_2来存储不是理想平方的数字。

• 函数calculate()填充向量vec并设置sett和sett_2。分隔为完美正方形，非完美正方形和幂> 3的数字。

• 使用for循环的遍历从i = 2到i <size。

• 插入完美力量i * i进行结算。

• 如果！= ）返回true，那么我是一个完美的正方形并且存在于sett中，所以什么也不做。sett.find(i)sett.end()

• 循环运行，直到当前数字的幂保持小于大。

• 将奇数幂插入到sett_2中，因为偶数幂是完美的平方且处于sett中。

• 最后，使用for循环将排序后的sett_2值插入向量vec。

• 函数GCD_1（long int开始，long int结束）将范围作为输入，并返回质数的GCD幂等于1的范围内的数字计数。

• 致电calculate()。

• 计算范围为per_sq = floor（sqrtl(end)）-floor（sqrtl(start-1)）的完美平方。

• 在使用VEC开始UPPER_BOUND的计算上限值（，，结束） - 。vec.begin()vec.end()vec.begin()

• 在使用VEC =底部LOWER_BOUND（端的同样低的值，，启动） - 。vec.begin()vec.end()vec.begin()

• 按照per_pow = per_sq +（上-下）计算完美功效。

• 答案将是count =（end-start + 1）-per_pow。

• 最后返回结果计数。

示例

#include <bits/stdc++.h>
using namespace std;
#define size 1000005
#define large 1e18

vector < long int > vec;
set < long int > sett;
set < long int > sett_2;

void calculate() {
   for (long int i = 2; i < size; i++) {
      sett.insert(i * i);
      if (sett.find(i) != sett.end()) {
         continue;
      }
      long int total = i;
      while (i * i <= large / total) {
         total *= (i * i);
         sett_2.insert(total);
      }
   }
   for (auto it: sett_2) {
      vec.push_back(it);
   }
}

long int GCD_1(long int start, long int end) {
   calculate();

   long int per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1));
   long int top = upper_bound(vec.begin(), vec.end(), end) - vec.begin();
   long int bottom = lower_bound(vec.begin(), vec.end(), start) - vec.begin();
   long int per_pow = per_sq + (top - bottom);
   long int count = (end - start + 1) - per_pow;
   return count;
}
int main() {
   long int start = 10, end = 40;
   cout << "GCD的质因子的幂等于1的范围内的数量计数是： " << GCD_1(start, end);
   return 0;
}

如果我们运行上面的代码，它将生成以下输出-

输出结果

GCD的质因子的幂等于1的范围内的数量计数是： 7