C++ Coprimes问题.优化代码

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