In C++, translate the following into Chinese: Count the number of numbers between L and R that are relatively prime to P

In the world of computer programming, finding the number of numbers in a given range that is coprime to a specific number can be a common task. Relatively prime numbers, also known as relative prime numbers, are numbers that have no common factors other than 1. In this article, we will explore finding the number of numbers that are relatively prime to a specific number P between given integers L and R by using C language.

grammar

We will first outline the syntax of the methods we will use in the following code examples -

int countCoprimes(int L, int R, int P);

algorithm

The algorithm we will use to calculate the number of coprime numbers is as follows −

• Initialize the variable count to 0, which is used to store the count of coprime numbers.

• Iterate each number num starting from L until R.

• For each num, check whether it is relatively prime with P.

• If num and P are relatively prime, increase the count by 1.

• Return the final value of count.

Method 1: Naive method

The first method we will discuss is the naive method. In order to verify coprimeness with P using Euclidean's algorithm, this method requires iteratively checking each number within a specified range.

The Chinese translation of

Example

is:

Example

#include <iostream>

int countCoprimes(int L, int R, int P) {
   int count = 0;
   for (int num = L; num <= R; num++) {
      int a = num;
      int b = P;
      while (b != 0) {
         int temp = b;
         b = a % b;
         a = temp;
      }
      if (a == 1)
         count++;
   }
   return count;
}

int main() {
   int L = 1; // Set the starting range value
   int R = 100; // Set the ending range value
   int P = 7; // Set the value of P
   
   int result = countCoprimes(L, R, P);
    
   std::cout << "Count of numbers between " << L << " and " << R << " coprime with " << P << ": " << result << std::endl;
   
   return 0;
}

Output

Count of numbers between 1 and 100 coprime with 7: 86

The Chinese translation of

Explanation

is:

Explanation

The countCoprimes function accepts three parameters: L (starting range value), R (ending range value) and P (value of P).

Inside the countCoprimes function, we initialize a variable count to 0, which will store the count of coprime numbers.

The for loop iterates each number num from L to R.

In the loop, we initialize the variables a and b to num and P respectively.

We use the Euclidean algorithm in the while loop to find the greatest common divisor (GCD) of a and b by repeatedly exchanging and performing modular operations.

If GCD (stored in a) is equal to 1, this means that num and P are co-prime. In this case, we increment the count variable.

We finalize our count value by carefully iterating through all the numbers and returning it when complete.

Main functions thoughtfully assign appropriate values ​​to L, R and P variables.

We then call the countCoprimes function with the provided value and store the result in the result variable.

Finally, we display the result, which is the count of numbers that are relatively prime to P between L and R.

Method 2: Prime factor decomposition

This strategy involves exploiting prime factorization of P to accurately calculate the number of coprime integers that fall between L and R.

The Chinese translation of

Example

is:

Example

#include <iostream>
#include <unordered_set>

int countCoprimes(int L, int R, int P) {
   std::unordered_set<int> factors;
   int tempP = P;

   for (int i = 2; i * i <= tempP; i++) {
      while (tempP % i == 0) {
         factors.insert(i);
         tempP /= i;
      }
   }

   if (tempP > 1)
      factors.insert(tempP);

   int count = 0;
   for (int num = L; num <= R; num++) {
      bool isCoprime = true;
      for (int factor : factors) {
         if (num % factor == 0) {
            isCoprime = false;
            break;
         }
      }
      if (isCoprime)
         count++;
   }

   return count;
}

int main() {
   int L = 1; // Set the starting range value
   int R = 100; // Set the ending range value
   int P = 7; // Set the value of P

   int result = countCoprimes(L, R, P);

   std::cout << "Count of numbers between " << L << " and " << R << " coprime with " << P << ": " << result << std::endl;

   return 0;
}

Output

Count of numbers between 1 and 100 coprime with 7: 86

The Chinese translation of

Explanation

is:

Explanation

The countCoprimes function accepts three parameters: L (starting range value), R (ending range value) and P (value of P).

We create an unordered factor set to store the prime factors of P. We initialize a temporary variable tempP to P.

We iterate from 2 to the square root of tempP. If tempP is divisible by i, we add i to the set of factors and divide tempP by i until tempP is no longer divisible by i.

If tempP is greater than 1 after the above loop, it means that it is a prime number and should be added to the factor.

We initialize the variable count to 0, which will store the count of coprime numbers.

We iterate over each number num from L to R and check if it is divisible by any factor in the set factors. If we can, we label it non-coprime.

After completing the iteration of all numbers, the resulting count will be returned as the final value. As for the main function, it initializes L, R and P with the specified values.

We then call the countCoprimes function with the provided value and store the result in the result variable.

Finally, we display the result, which is the count of numbers that are relatively prime to P between L and R.

in conclusion

Calculating coprime numbers within a specified range L-R, and satisfying a specific value P, is a good challenge for programmers - but at the code level, what is the best approach? As part of this article, we take a deep dive into two C use cases that offer real efficiencies when solving problems like this. First, by iterating over all values ​​within the target interval and using the Euclidean algorithm to check whether the numbers match as coprime numbers; and also by using the Euler function method, which uses an optimization strategy. Regardless of which method you use, whether you can get the most out of it depends largely on contextual factors, like the numbers you choose and the intervals you specify, but choosing wisely between the two possible methods can really speed things up overall. The execution speed of the program. For coders looking to add technical savvy to their technical skills and creative problem-solving abilities, mastering coprime number counting using C through these methods may be just what they need.

The above is the detailed content of In C++, translate the following into Chinese: Count the number of numbers between L and R that are relatively prime to P. For more information, please follow other related articles on the PHP Chinese website!