資料結構
網路
RDBMS
作業系統
Java
MS Excel
IOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究在 C++ 中查詢 1 到 N 中的幾乎素數
假設我們有一個數字 N。我們必須在範圍 1 到 N 中查詢幾乎素數。當一個數字恰好有兩個不同的因子時，它被稱為幾乎素數。這些數字可以擁有任意數量的非素數因子，但必須有兩個素數因子。因此，如果 N 為 2，那麼輸出將為 2。有兩個數字 6 和 10。
這裡我們將採用埃拉託斯特尼篩法。請檢視以下實現以獲得更好的想法。
示例
#include<iostream>
#define N 100005
using namespace std;
bool prime[N];
void SieveOfEratosthenes() {
for(int i = 0; i<N; i++)
prime[i] = true;
prime[1] = false;
for (int i = 2; i * i < N; i++) {
if (prime[i] == true) {
for (int j = i * 2; j < N; j += i)
prime[j] = false;
}
}
}
int countAlmostPrime(int n) {
int result = 0;
for (int i = 6; i <= n; i++) {
int div_count = 0;
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
if (j * j == i) {
if (prime[j])
div_count++;
}else {
if (prime[j])
div_count++;
if (prime[i / j])
div_count++;
}
}
}
if (div_count == 2)
result++;
}
return result;
}
int main() {
SieveOfEratosthenes();
int n = 21;
cout << "Number of almost primes in range 1 to "<<n << " is: " << countAlmostPrime(n);
}輸出
Number of almost primes in range 1 to 21 is: 8
更新於：18-12-2019
298 次瀏覽
廣告