จำนวนปัจจัยเฉพาะสูงสุดใน C++

ภารกิจคือการค้นหาจำนวนสูงสุดของปัจจัยเฉพาะเฉพาะที่ตัวเลขสามารถมีได้ในช่วง [1, N] โดยที่ N จะได้รับ

ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -

ป้อนข้อมูล − N=100

ผลลัพธ์ − 3

คำอธิบาย − ให้เราหา 30 ในช่วง [1, 100]

30 =3 * 2 * 5 =ปัจจัยเฉพาะเฉพาะ ดังนั้น ในช่วง [1, 100] จะพบปัจจัยเฉพาะสูงสุด 3 ตัว

ป้อนข้อมูล − N=300

ผลผลิต − 4

แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้

ในฟังก์ชัน MaxPrime() เราจะตรวจสอบก่อนว่า (N <2) ถ้าใช่ก็แค่คืนค่าศูนย์ มิฉะนั้น ให้ดำเนินการต่อ
จากนั้นเราจะใช้ตะแกรง Eratosthenes เพื่อหาจำนวนเฉพาะทั้งหมดก่อนจำนวนที่กำหนด N
เริ่มต้นสองตัวแปร pro=1 และ max=0 ของประเภท int เพื่อจัดเก็บผลิตภัณฑ์และคำตอบสุดท้ายตามลำดับ
ภายในตะแกรงของ Eratosthenes เราจะคูณจำนวนเฉพาะชุดแรกจนกว่าผลคูณจะยังคงน้อยกว่า N โดยการเขียน − pro=*p;
ตรวจสอบว่า (pro> N) ถ้าใช่ ให้คืนค่า max และเพิ่ม 1 เป็น max.
นอกตะแกรง ให้คืนสูงสุดด้วย

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int MaxPrime(int N){
   if (N < 2)
      return 0;
   // Using Sieve of Eratosthenes
   bool Arr[N+1];
   memset(Arr, true, sizeof(Arr));
   int pro = 1, max = 0;
   for (int p=2; p*p<=N; p++){
      if (Arr[p] == true){
         for (int i=p*2; i<=N; i += p)
            Arr[i] = false;
         /*Multiply first set of prime numbers while product remains smaller than N*/
         pro *= p;
         if (pro > N)
            return max;
         max++;
      }
   }
   return max;
}
//Main function
int main(){
   int N = 300;
   cout << MaxPrime(N);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -