写一个求约数个数的c++代码
时间: 2024-05-05 22:18:40 浏览: 14
好的,以下是一个求约数个数的c代码:
```
#include <stdio.h>
int get_divisor_count(int num){
int divisor_count = 0;
int i;
for(i = 1; i <= num; i++){
if(num % i == 0){
divisor_count++;
}
}
return divisor_count;
}
int main(){
int num = 24;
int divisor_count;
divisor_count = get_divisor_count(num);
printf("Number of divisors of %d is %d", num, divisor_count);
return 0;
}
```
请问有什么其它问题需要我回答吗?
相关问题
用c++代码写一个求公约数
以下是用 C 代码写一个求公约数的示例:
```
#include <stdio.h>
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
int a, b;
printf("请输入两个整数:\n");
scanf("%d %d", &a, &b);
printf("它们的最大公约数是:%d\n", gcd(a, b));
return 0;
}
```
这个程序使用递归的方式实现了求两个整数的最大公约数。
请生成线性筛求约数个数的c++代码
以下是使用线性筛求约数个数的 C++ 代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000000;
vector<int> primes; // 存储素数
int factor[MAXN + 1]; // 存储最小素因子
void linear_sieve() {
for (int i = 2; i <= MAXN; i++) {
if (factor[i] == 0) {
factor[i] = i; // i 是素数
primes.push_back(i);
}
for (int j = 0; j < primes.size() && primes[j] <= factor[i] && i * primes[j] <= MAXN; j++) {
factor[i * primes[j]] = primes[j];
}
}
}
int count_divisors(int n) {
int cnt = 1;
for (int i = 0; i < primes.size() && primes[i] * primes[i] <= n; i++) {
int p = primes[i], e = 0;
while (n % p == 0) {
n /= p;
e++;
}
cnt *= e + 1;
}
if (n > 1) cnt *= 2;
return cnt;
}
int main() {
linear_sieve();
int n;
cin >> n;
cout << count_divisors(n) << endl;
return 0;
}
```
该程序先使用线性筛法得到 $1$ 到 $10^6$ 之间的素数,同时记录每个数的最小素因子。接着通过遍历素数,统计 $n$ 的约数个数。具体地,设 $n = \prod_{i=1}^k p_i^{e_i}$ 是 $n$ 的质因数分解式,则 $n$ 的约数个数为 $\prod_{i=1}^k (e_i + 1)$。注意当 $n$ 的质因子中存在大于 $\sqrt{n}$ 的数时,还需要再乘以 $2$。
相关推荐
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)