Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 소인수의 거듭제곱의 GCD가 1인 범위의 숫자 세기

<시간/>

양의 정수 범위를 나타내는 두 개의 숫자 시작과 끝이 주어집니다. 목표는 [start, end] 범위에 있는 모든 숫자의 개수를 찾고 해당 숫자의 모든 소인수가 GCD가 1이 되도록 거듭제곱이 되도록 소인수분해를 갖는 것입니다.

숫자가 2 p 로 소인수분해되는 경우 * 3 q * 5 r ... .. 그런 다음 p,q,r의 거듭제곱은 ...gcd=1이어야 합니다.

예를 들어 이해합시다.

예

입력 - 시작 =1, 끝 =10

출력 - GCD가 1인 소인수의 거듭제곱을 갖는 범위의 숫자 개수는 다음과 같습니다. 6

설명 - 숫자는 다음과 같습니다.

2( 2 1 ), 3( 3 1 ), 5( 5 1 ), 7( 7 1 ), 8( 2 3 ) 및 10( 2 1 *5 1 ). 각 소인수분해의 모든 거듭제곱은 gcd가 1입니다.

입력 - 시작 =11, 끝 =20

출력 - GCD가 1인 소인수의 거듭제곱을 갖는 범위의 숫자 개수는 다음과 같습니다. 9

설명 - 숫자는 다음과 같습니다.

11 ( 11 1 ), 12( 3 1 *2 2 ), 13( 13 1 ), 14( 2 1 *7 1 ), 15( 3 1 *5 1 ), 17( 17 1 ), 18( 2 1 *3 2 ), 19( 19 1 ) 및 20( 2 2 *5 1 ). 각 소인수분해의 모든 거듭제곱은 gcd가 1입니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

이 접근 방식에서는 시작부터 끝까지 완전하지 않은 범위의 모든 숫자를 계산합니다. 불완전한 힘은 위의 조건을 만족할 것이기 때문입니다. 이를 위해 우리는 모든 완벽한 능력을 찾아 총계에서 제거할 것입니다.

답은 =start-end +1 - (범위[start,end]에서 완전제곱수인 숫자의 개수)입니다.

  • 범위 변수를 입력으로 시작하고 끝냅니다.
  • 벡터 vec를 사용하여 3보다 큰 거듭제곱을 저장합니다.
  • 완전제곱수를 저장하려면 집합을 사용하세요.
  • 완전제곱이 아닌 숫자를 저장하려면 sett_2 집합을 사용하세요.
  • 함수 계산()은 벡터 vec를 채우고 sett 및 sett_2를 설정합니다. 완전제곱수, 비완전제곱수 및 거듭제곱인 수를 구분하려면>3.
  • i=2에서 i 까지 for 루프를 사용하는 순회
  • 설정할 완전 거듭제곱 i*i를 삽입합니다.
  • IF sett.find(i) !=sett.end())가 true를 반환하면 i는 완전제곱수이고 sett에 있으므로 아무 것도 하지 않습니다.
  • 현재 숫자의 거듭제곱이 큰 값보다 작아질 때까지 while 루프를 실행합니다.
  • 짝수 거듭제곱은 완전제곱이고 집합이므로 sett_2에 홀수 거듭제곱을 삽입합니다.
  • 마지막에 for 루프를 사용하여 벡터 vec에 sett_2의 정렬된 값을 삽입합니다.
  • 함수 GCD_1(long int start, long int end)은 범위를 입력으로 사용하고 GCD가 1인 소인수 거듭제곱을 갖는 범위의 숫자 개수를 반환합니다.
  • calc()를 호출합니다.
  • per_sq =floor(sqrtl(end)) - floor(sqrtl(start - 1))과 같은 범위의 완전제곱수를 계산합니다.
  • upper_bound(vec.begin(), vec.end(), end) - vec.begin()을 사용하여 vec에서 시작의 상위 값을 계산합니다.
  • bottom =lower_bound(vec.begin(), vec.end(), start) - vec.begin()을 사용하여 vec의 end 값이 유사하게 낮습니다.
  • per_pow =per_sq + (상단 - 하단)으로 완전 거듭제곱을 계산합니다.
  • 답은 count =(end - start + 1) - per_pow입니다.
  • 마지막에 결과로 카운트를 반환합니다.

예시

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

위의 코드를 실행하면 다음 출력이 생성됩니다 -

출력

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