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

Answer 2

На одноядерном компьютере он не станет намного быстрее, чем сейчас. Таким образом, вы хотите использовать несколько ядер или даже несколько компьютеров. Распараллелить и распределить.

Поскольку каждая пара чисел, для которой вы хотите рассчитать GCD, не связана с какой-либо другой парой чисел, вы можете легко модифицировать свою программу для использования нескольких ядер с помощью потоков.

Если это все еще не достаточно быстро, вам лучше подумать об использовании распределенных вычислений, распределив работу на множество компьютеров. Это немного сложнее, но лучше всего повысить производительность, если пространство поиска велико.

Answer 3

Попробуйте попробовать с double с.В нем говорится, что деления с двойными числами быстрее на типичных чипах Intel.Целочисленное деление - самая медленная инструкция.Это проблема куриного яйца.Никто не использует их, потому что они медленные, а Intel не делает это быстрее, потому что никто не использует их.