数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中计算范围内公约数为素数因子幂的1的数字
给定两个数字start和end，代表一个正整数范围。目标是查找位于范围[start,end]内，并且其素因子分解中所有素因子的幂的公约数都等于1的数字个数。
如果一个数字的素因子分解为2p * 3q * 5r……，那么幂p、q、r……的公约数应为1。
让我们通过例子来理解。
例如
输入 - start = 1, end = 10
输出 - 范围内公约数为素数因子幂的1的数字个数为：6
解释 - 这些数字是
2 (21), 3 (31), 5 (51), 7 (71), 8 (23) 和 10 (21*51)。每个素因子分解的幂的公约数都为1。
输入 - start = 11, end = 20
输出 - 范围内公约数为素数因子幂的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)。每个素因子分解的幂的公约数都为1。
下面程序中使用的算法如下
在这个方法中，我们将计算从start到end范围内不是完全幂的数字个数。因为非完全幂将满足上述条件。为此，我们将找到所有完全幂，并将它们从总数中减去。
答案将是 = start-end +1 - (范围[start,end]内是完全幂的数字个数)。
- 将范围变量start和end作为输入。
- 使用向量vec存储大于3的幂。
- 使用集合sett存储完全平方数。
- 使用集合sett_2存储不是完全平方数的数字。
- 函数calculate()填充向量vec和集合sett和sett_2。用于分离完全平方数、非完全平方数和幂>3的数字。
- 使用for循环从i=2遍历到i<size。
- 将完全幂i*i插入sett。
- 如果sett.find(i) != sett.end())返回true，则i是完全平方数，存在于sett中，因此无需执行任何操作。
- 运行while循环，直到当前数字的幂小于large。
- 将奇数幂插入sett_2，因为偶数幂是完全平方数，存在于sett中。
- 最后，使用for循环将sett_2的排序值插入向量vec。
- 函数GCD_1(long int start, long int end)以范围作为输入，并返回范围内公约数为素数因子幂的1的数字个数。
- 调用calculate()。
- 计算范围内的完全平方数为per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1))。
- 使用upper_bound(vec.begin(), vec.end(), end) - vec.begin()计算vec中start的上界值。
- 类似地，使用bottom = lower_bound(vec.begin(), vec.end(), start) - vec.begin()计算vec中end的下界值。
- 计算完全幂为per_pow = per_sq + (top - bottom)。
- 答案将是count = (end - start + 1) - per_pow。
- 最后返回count作为结果。
示例
#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 << "Count of numbers in a range having GCD of powers of prime factors equal to 1 are: " << GCD_1(start, end);
return 0;
}如果我们运行上述代码，它将生成以下输出：
输出
Count of numbers in a range having GCD of powers of prime factors equal to 1 are: 7
更新于：2021年1月29日
78 次浏览
广告