数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究统计所有小于 10^6 且最小质因数为 N 的数字（C++）
假设给定一个质数，例如 num，任务是计算所有小于 10^6 且最小质因数等于 num 的数字的数量。
例如
Input − num = 7 Output − Number of prime factors = 38095 Input − num = 3 Output − Number of prime factors = 16666
下面程序中使用的方案如下
输入数字，例如 num
启动循环，从 i 为 2 开始，i 应小于或等于最大值，并递增 i 的值
在循环内部，检查 s_prime[i] 是否等于 0
创建循环，将 j 设置为 i * 2，j 应小于或等于最大值，并将 j 设置为 j + i
现在检查，s_prime[j] 是否等于 1
设置 s_prime[j] 为 1
将 s_count[i] 递增 1
打印结果
示例
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
// a sieve for prime number and
// to count the number of prime
int s_prime[MAX + 4] = { 0 }, s_count[MAX + 4] = { 0 };
void create_sieve(){
// As 1 is not a prime number
s_prime[1] = 1;
// creating the sieve
for (int i = 2; i <= MAX; i++){
// if i is a prime number
if (s_prime[i] == 0){
for (int j = i * 2; j <= MAX; j += i){
// if i is the least prime factor
if (s_prime[j] == 0){
// The number j is not a prime
s_prime[j] = 1;
// counting the numbers whose least prime factor
// is i
s_count[i]++;
}
}
}
}
}
int main(){
// create the sieve
create_sieve();
int N = 7;
cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
N = 3;
cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Number of prime factors = 38095 Number of prime factors = 166667
更新于：2020年5月15日
151 次查看
广告