Số lượng tối đa các thừa số nguyên tố duy nhất trong C ++

Nhiệm vụ được giao là tìm số lượng tối đa các thừa số nguyên tố duy nhất mà một số có thể có trong phạm vi [1, N] trong đó N được cho.

Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -

Đầu vào - N =100

Đầu ra - 3

Giải thích - Hãy để chúng tôi lấy 30 trong phạm vi [1, 100]

30 =3 * 2 * 5 =thừa số nguyên tố duy nhất. Do đó, trong phạm vi [1, 100] có thể tìm thấy tối đa 3 yếu tố duy nhất.

Đầu vào - N =300

Đầu ra - 4

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Trong hàm MaxPrime (), đầu tiên chúng ta sẽ kiểm tra xem (N <2). Nếu vậy thì chỉ cần trả về 0, nếu không thì tiếp tục.
Sau đó, chúng tôi sẽ sử dụng sàng của Eratosthenes để tìm ra tất cả các số nguyên tố trước số N.
Khởi tạo hai biến pro =1 và max =0 kiểu int để lưu trữ sản phẩm và câu trả lời cuối cùng tương ứng.
Bên trong sàng của Eratosthenes, chúng ta sẽ nhân tập hợp các số nguyên tố đầu tiên cho đến khi tích số còn lại nhỏ hơn N bằng cách viết - pro =* p;
Kiểm tra xem (pro> N). Nếu vậy, hãy trả về giá trị tối đa và thêm 1 vào giá trị tối đa.
Bên ngoài sàng, cũng trả về giá trị tối đa.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -