เราได้จำนวนเฉพาะ สมมุติว่า 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
-
ภายในลูป ให้ตรวจสอบว่า s_prime[i] =0
-
สร้างลูปตั้งค่า j เป็น i * 2 และ j ควรน้อยกว่าเท่ากับ max และตั้งค่า 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
