计算C ++中质数因子的GCD等于1的范围内的数字
给定两个数字，开始和结束分别代表一个正整数范围。目标是找到位于[start，end]范围内并具有素数分解的所有数字的计数，以使该数量的所有素数具有幂，使得它们的GCD为1。
如果一个数的质数分解为2p *3q*5r…..则幂p，q，r...应具有gcd=1。
让我们通过示例来理解。
例如
输入-开始=1，结束=10
输出-质数幂的GCD等于1的范围内的数量计数是：6
说明-这些数字是：
2（21），3（31），5（51），7（71），8（23）和10（21*51）。每个素数分解的所有幂的gcd为1。
输入-开始=11，结束=20
输出-质数幂的GCD等于1的范围内的数量计数是：9
说明-这些数字是：
11（111），12（31*22），13（131），14（21*71），15（31*51），17（171），18（21*32），19（191 ）和20（22*51）。每个素数分解的所有幂的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（longint开始，longint结束）将范围作为输入，并返回质数的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