Если число в виде string, то можно столбиком:

2

(4 ответов, оставленных в Algo)

Алгоритм очень простой, но есть нюансы в начальных значениях. Я считаю, что наиболее адекватно он представлен в демофайле пакета GMP (папка demos, файл factorize.c). Там правда написано все в стандарте обычного С, но можно легко переделать под С++.

void factor_using_pollard_rho (mpz_t n, unsigned long a, struct factors *factors)
{
  mpz_t x, z, y, P;
  mpz_t t, t2;
  unsigned long long k, l, i;

  if (flag_verbose > 0)
    {
      printf ("[pollard-rho (%lu)] ", a);
    }

  mpz_inits (t, t2, NULL);
  mpz_init_set_si (y, 2);
  mpz_init_set_si (x, 2);
  mpz_init_set_si (z, 2);
  mpz_init_set_ui (P, 1);
  k = 1;
  l = 1;

  while (mpz_cmp_ui (n, 1) != 0)
    {
      for (;;)
    {
      do
        {
          mpz_mul (t, x, x);
          mpz_mod (x, t, n);
          mpz_add_ui (x, x, a);

          mpz_sub (t, z, x);
          mpz_mul (t2, P, t);
          mpz_mod (P, t2, n);

          if (k % 32 == 1)
        {
          mpz_gcd (t, P, n);
          if (mpz_cmp_ui (t, 1) != 0)
            goto factor_found;
          mpz_set (y, x);
        }
        }
      while (--k != 0);

      mpz_set (z, x);
      k = l;
      l = 2 * l;
      for (i = 0; i < k; i++)
        {
          mpz_mul (t, x, x);
          mpz_mod (x, t, n);
          mpz_add_ui (x, x, a);
        }
      mpz_set (y, x);
    }

    factor_found:
      do
    {
      mpz_mul (t, y, y);
      mpz_mod (y, t, n);
      mpz_add_ui (y, y, a);

      mpz_sub (t, z, y);
      mpz_gcd (t, t, n);
    }
      while (mpz_cmp_ui (t, 1) == 0);

      mpz_divexact (n, n, t);    /* divide by t, before t is overwritten */

      if (!mp_prime_p (t))
    {
      if (flag_verbose > 0)
        {
          printf ("[composite factor--restarting pollard-rho] ");
        }
      factor_using_pollard_rho (t, a + 1, factors);
    }
      else
    {
      factor_insert (factors, t);
    }

      if (mp_prime_p (n))
    {
      factor_insert (factors, n);
      break;
    }

      mpz_mod (x, x, n);
      mpz_mod (z, z, n);
      mpz_mod (y, y, n);
    }

  mpz_clears (P, t2, t, z, x, y, NULL);
}

3

(1 ответов, оставленных в Algo)

А столбиком не пробовал?

4

(3 ответов, оставленных в Algo)

Забудь про методы типа Поларда и обрати внимание на модификации метода Ферма, например Диксона или Померанца.