資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告