Нахождение простых факторов в C - PullRequest
Новая
       3

Нахождение простых факторов в C

0 голосов
/ 12 марта 2011

Я пытаюсь сгенерировать все простые множители числа n.Когда я даю ему число 126, оно дает мне 2, 3 и 7, но когда я даю ему, скажем 8, оно дает мне 2, 4 и 8. Есть идеи относительно того, что я делаю неправильно?

int findPrime(unsigned long n)
{
  int testDivisor, i;
  i = 0;
  testDivisor = 2;
  while (testDivisor < n + 1)
  {
    if ((testDivisor * testDivisor) > n)
    {
    //If the test divisor squared is greater than the current n, then 
    //the current n is either 1 or prime. Save it if prime and return
    }
    if (((n % testDivisor) == 0))
    {
      prime[i] = testDivisor;
      if (DEBUG == 1) printf("prime[%d] = %d\n", i, prime[i]);
      i++;
      n = n / testDivisor;
    }
    testDivisor++;
  }
  return i;
}

Ответы [ 4 ]

3 голосов
/ 12 марта 2011

Вы увеличиваете testDivisor, даже если вы смогли поделить n на него. Увеличивайте его только тогда, когда он больше не делится. Это приведет к 2,2,2, так что вам придется немного изменить его, чтобы не хранить дубликаты, но так как это домашнее задание, я думаю, вы должны выяснить это самостоятельно:)

2 голосов
/ 12 марта 2011

Это основано на алгоритме, который ваш профессор сказал вам реализовать, или это ваша собственная эвристика?В случае, если это помогает, некоторые известные алгоритмы первичной факторизации - это квадратичное сито и сетчатое поле общего числа.

0 голосов
/ 21 ноября 2013

Вот код для поиска простого фактора: 

long GetPrimeFactors(long num, long *arrResult)
{
    long count = 0;
    long arr[MAX_SIZE];

    long i = 0;

    long idx = 0;

    for(i = 2; i <= num; i++)
    {
      if(IsPrimeNumber(i) == true)
          arr[count++] = i;
    }

    while(1)
    {
      if(IsPrimeNumber(num) == true)
      {
          arrResult[idx++] = num;
          break;
      }
      for(i = count - 1; i >= 0; i--)
      {
          if( (num % arr[i]) == 0)
          {
            arrResult[idx++] = arr[i];
            num = num / arr[i];
            break;
          }
      }
    }
    return idx;
}

Ссылка: http://www.softwareandfinance.com/Turbo_C/Prime_Factor.html

0 голосов
/ 12 марта 2011

Прямо сейчас вы не проверяете, являются ли найденные вами делители простыми.Пока n % testDivisor == 0 вы считаете testDivisor главным фактором.Кроме того, вы делитесь только на testDivisor один раз.Вы можете исправить это несколькими способами, одним из которых будет замена оператора if (((n % testDivisor) == 0)) на while (((n % testDivisor) == 0)).

Исправление этого путем добавления цикла while также гарантирует, что вы не получите составные числа какделители, как будто они все еще делят n, меньший простой множитель должен был бы также разделить n, и цикл while для этого простого фактора не был бы ранним.

...