C++ 互质问题。优化代码

Question

您好，我想优化以下代码。它试图通过将它们与 n 进行比较来找到给定范围内的所有互素数。但我想让它运行得更快……有什么想法吗？

#include <iostream>

using namespace std;

int GCD(int a, int b)
{
    while( 1 )
    {
        a = a % b;
  if( a == 0 )
   return b;
  b = b % a;

        if( b == 0 )
   return a;
    }
}


int main(void){
 int t;
 cin >> t;
 for(int i=0; i<t; i++){
  int n,a,b;
  cin >> n >> a >> b;

  int c = 0;
  for(int j=a; j<=b; j++){
   if(GCD(j, n) == 1) c++;
  }

  cout << c << endl;
 }

 return 0;
}

Answer 1

这闻起来像家庭作业，所以只是一个提示。

这里不需要计算GCD。如果您可以对 n 进行因式分解(即使是尝试除以每个小于 2^16 的奇数的最粗略的方法)，那么您可以只计算碰巧不能除以 n 的因数的数字。

请注意，一个 32 位数字最多有 10 个因数(我们不需要记住给定质数在因式分解中使用了多少次)。

该怎么做？尝试使用包含 - 排除原则计算非互质数。您将最多检查 1023 个素数子集，对于每个子集，您需要计算范围内的乘法次数，这是每个子集的常数时间。

无论如何，我的代码现在可以立即运行:

liori:~/gg% time ./moje <<< "1 1003917915 1 1003917915"
328458240
./moje <<< "1 1003917915 1 1003917915"  0,00s user 0,00s system 0% cpu 0,002 total