Đếm các số trong một phạm vi có GCD lũy thừa của các thừa số nguyên tố bằng 1 trong C ++

Cho trước hai số bắt đầu và kết thúc đại diện cho một loạt các số nguyên dương. Mục đích là tìm số đếm của tất cả các số nằm trong phạm vi [bắt đầu, kết thúc] và có thừa số nguyên tố sao cho tất cả các thừa số nguyên tố của số đó đều có lũy thừa sao cho chúng có GCD là 1.

Nếu một số có thừa số nguyên tố là 2 ^p * 3 ^q * 5 ^r … .. Khi đó các lũy thừa p, q, r… nên có gcd =1.

Hãy cho chúng tôi hiểu với các ví dụ.

Ví dụ

Đầu vào - start =1, end =10

Đầu ra - Đếm các số trong dãy có GCD lũy thừa của các thừa số nguyên tố bằng 1 là:6

Giải thích - Các con số là:

2 (2 ¹ ), 3 (3 ¹ ), 5 (5 ¹ ), 7 (7 ¹ ), 8 (2 ³ ) và 10 (2 ¹ * 5 ¹ ). Tất cả các lũy thừa của mỗi thừa số nguyên tố có gcd là 1.

Đầu vào - start =11, end =20

Đầu ra - Đếm các số trong dãy có GCD lũy thừa của các thừa số nguyên tố bằng 1 là:9

Giải thích - Các con số là:

11 (11 ¹ ), 12 (3 ¹ * 2 ² ), 13 (13 ¹ ), 14 (2 ¹ * 7 ¹ ), 15 (3 ¹ * 5 ¹ ), 17 (17 ¹ ), 18 (2 ¹ * 3 ² ), 19 (19 ¹ ) và 20 (2 ² * 5 ¹ ). Tất cả các lũy thừa của mỗi thừa số nguyên tố có gcd là 1.

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

Trong cách tiếp cận này, chúng tôi sẽ đếm tất cả các số trong phạm vi bắt đầu đến kết thúc không phải là lũy thừa hoàn hảo. Như các lũy thừa không hoàn hảo sẽ thỏa mãn điều kiện trên. Đối với điều này, chúng tôi sẽ tìm tất cả các quyền hạn hoàn hảo và xóa chúng khỏi tổng số.

Câu trả lời sẽ là =start-end +1 - (số lượng các số trong phạm vi [bắt đầu, kết thúc] là lũy thừa hoàn hảo).

Lấy các biến phạm vi bắt đầu và kết thúc làm đầu vào.
Lấy vec-tơ vec-tơ để lưu trữ các lũy thừa lớn hơn 3.
Thực hiện một thiết lập bộ để lưu trữ các số là hình vuông hoàn hảo.
Thực hiện một bộ định nghĩa 2 để lưu trữ các số không phải là hình vuông hoàn hảo.
Hàm tính toán () điền vec vec tơ và đặt các thiết lập và thiết lập_2. Để phân tách các số là bình phương hoàn hảo, bình phương không hoàn hảo và lũy thừa> 3.
Travers sử dụng vòng lặp for từ i =2 đến i
Chèn sức mạnh hoàn hảo i * i để thiết lập.
NẾU setting.find (i)! =Regi.end ()) trả về true thì tôi là một hình vuông hoàn hảo và có mặt trong setting nên không cần làm gì cả.
Chạy vòng lặp while cho đến khi công suất của số hiện tại không còn lớn hơn.
Chèn lũy thừa lẻ vào thiết lập_2 vì lũy thừa chẵn là những hình vuông hoàn hảo và trong cài đặt.
Ở cuối, hãy chèn các giá trị đã sắp xếp của setting_2 vào vec-tơ vec bằng cách sử dụng vòng lặp for.
Hàm GCD_1 (long int start, long int end) lấy dải ô làm đầu vào và trả về số lượng các số trong một dải ô có GCD là lũy thừa của các thừa số nguyên tố bằng 1.
Gọi tính toán ().
Tính toán các ô vuông hoàn hảo trong phạm vi như per_sq =floor (sqrtl (end)) - floor (sqrtl (start - 1)).
Tính giá trị trên của start trong vec bằng cách sử dụng upper_bound (vec.begin (), vec.end (), end) - vec.begin ().
Tương tự, giá trị thấp hơn của end trong vec sử dụng bottom =Lower_bound (vec.begin (), vec.end (), start) - vec.begin ().
Tính lũy thừa hoàn hảo dưới dạng per_pow =per_sq + (trên - dưới).
Câu trả lời sẽ được tính =(end - start + 1) - per_pow.
Kết quả trả về là kết quả cuối cùng.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
#define size 1000005
#define large 1e18

vector < long int > vec;
set < long int > sett;
set < long int > sett_2;

void calculate() {
   for (long int i = 2; i < size; i++) {
      sett.insert(i * i);
      if (sett.find(i) != sett.end()) {
         continue;
      }
      long int total = i;
      while (i * i <= large / total) {
         total *= (i * i);
         sett_2.insert(total);
      }
   }
   for (auto it: sett_2) {
      vec.push_back(it);
   }
}

long int GCD_1(long int start, long int end) {
   calculate();

   long int per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1));
   long int top = upper_bound(vec.begin(), vec.end(), end) - vec.begin();
   long int bottom = lower_bound(vec.begin(), vec.end(), start) - vec.begin();
   long int per_pow = per_sq + (top - bottom);
   long int count = (end - start + 1) - per_pow;
   return count;
}
int main() {
   long int start = 10, end = 40;
   cout << "Count of numbers in a range having GCD of powers of prime factors equal to 1 are: " << GCD_1(start, end);
   return 0;
}

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Đầu ra

Count of numbers in a range having GCD of powers of prime factors equal to 1 are: 7