資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用篩法O(log n)進行多次查詢的C++素數分解
在這個問題中，我們需要建立一個程式來計算 *使用篩法O(log n)進行多次查詢的素數分解*。
因為一般方法需要O(sqrt(n))的時間，對於多次查詢，這會極大地增加所需時間。
讓我們先回顧一下：
素數分解 一個數的素數分解只包含素數因子，而不包含這些素數因子的任何乘積。
埃拉託斯特尼篩法 是一種在給定範圍內生成所有素數的演算法。
解決方案方法
問題的解決方案是找到能整除該數的最小因子，將其儲存為因子，並透過將其除以該因子來更新該數。這個過程遞迴地進行，直到該數在除法後變為1，這意味著沒有其他可能的因子。
計算使用 *埃拉託斯特尼篩法* 進行，這降低了查詢最小素數因子的時間複雜度。
程式說明我們解決方案的工作原理
示例
#include <iostream>
using namespace std;
int primes[100001];
void sieveOfEratosthenes(int N) {
N+=2;
primes[1] = 1;
for (int i=2; i<N; i++)
primes[i] = i;
for (int i=4; i<N; i+=2)
primes[i] = 2;
for (int i=3; i*i<N; i++) {
if (primes[i] == i) {
for (int j=i*i; j<N; j+=i)
if (primes[j]==j)
primes[j] = i;
}
}
}
void findPrimeFactors(int num) {
sieveOfEratosthenes(num);
int factor;
while (num != 1) {
factor = primes[num];
cout<<factor<<" ";
num /= factor;
}
}
int main() {
int N = 45214;
cout<<"Prime factorization of the number "<<N<<" using sieve is ";
findPrimeFactors(N);
return 0;
}輸出
Prime factorization of the number 45214 using sieve is 2 13 37 47
更新於：2021年1月27日
2K+ 次瀏覽
廣告