Нахождение наибольшего простого множителя составного числа в c

Question

Я принимаю составное число в качестве ввода. Я хочу напечатать все его факторы, а также самый большой главный фактор из этого числа. Я написал следующий код. Он работает нормально до числа 51. Но если введено любое число больше 51, выводится неправильный вывод. как я могу исправить свой код?

#include<stdio.h>
void main()
{
 int i, j, b=2, c;
 printf("\nEnter a composite number: ");
 scanf("%d", &c);
 printf("Factors: ");

 for(i=1; i<=c/2; i++)
 {
  if(c%i==0)
  {
   printf("%d ", i);
   for(j=1; j<=i; j++)
   {
    if(i%j > 0)
    {
     b = i;
    }
    if(b%3==0)
     b = 3;
    else if(b%2==0)
     b = 2;
    else if(b%5==0)
     b = 5;
   }
  }
 }
 printf("%d\nLargest prime factor: %d\n", c, b);
}

Answer 1

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

Подсказка № 1: Если делитель является делителем n, то n / делитель также является делителем n.Например, 100/2 = 50 с остатком 0, поэтому 2 - это делитель 100. Но это также означает, что 50 - это делитель 100.

Подсказка # 2 Учитывая Подсказка #1, это означает, что мы можем переходить от i = 2 к i * i <= n при проверке простых факторов.Например, если мы проверяем число 100, то нам нужно только вернуться к 10 (10 * 10 - <= 100), потому что, используя подсказку # 1, мы получим все факторы.То есть: </p>

100 / 2 = 50, so 2 and 50 are factors
100 / 5 = 20, so 5 and 20 are factors
100 / 10 = 10, so 10 is a factor

Подсказка # 3 Поскольку мы заботимся только о простых множителях для n, достаточно просто найти первый множитель n, назвать его делителем, а затем мы можемРекурсивно найти другие факторы для п / делитель.Мы можем использовать подход sieve и отмечать факторы по мере их нахождения.

Подсказка # 4 Пример решения в C:

bool factors[100000];

void getprimefactors(int n) {
  // 0 and 1 are not prime
  if (n == 0 || n == 1) return;

  // find smallest number >= 2 that is a divisor of n (it will be a prime number)
  int divisor = 0;
  for(int i = 2; i*i <= n; ++i) {
    if (n % i == 0) {
      divisor = i;
      break;
    }
  }
  if (divisor == 0) {
    // we didn't find a divisor, so n is prime
    factors[n] = true;
    return;
  }

  // we found a divisor
  factors[divisor] = true;
  getprimefactors(n / divisor);
}

int main() {
  memset(factors,false,sizeof factors);
  int f = 1234;
  getprimefactors(f);
  int largest;
  printf("prime factors for %d:\n",f);
  for(int i = 2; i <= f/2; ++i) {
    if (factors[i]) {
      printf("%d\n",i);
      largest = i;
    }
  }
  printf("largest prime factor is %d\n",largest);
  return 0;
}

Вывод:

---------- Capture Output ----------
> "c:\windows\system32\cmd.exe" /c c:\temp\temp.exe
prime factors for 1234:
2
617
largest prime factor is 617
> Terminated with exit code 0.

Answer 2

Полагаю, вы делаете это, чтобы учиться, поэтому я надеюсь, что вы не возражаете против намека.

Я бы начал с пошагового алгоритма поиска числа, которое не удалось. Это показывает, где ошибка?

Answer 3

Вам нужно перекодировать, чтобы ваш код находил все простые числа заданного числа, а не просто вычислял простые числа 2,3 и 5. Другими словами, ваш код может работать только с тем числом, которым вы являетесь Вычисление является простым числом или кратным 2, 3 или 5. Но 7, 11, 13, 17, 19 также являются простыми числами - поэтому ваш код должен просто работать, находя все факторы определенного числа и возвращая Наибольший фактор, который в дальнейшем не делится.

Answer 4

Упрощение ответа dcp (итеративным способом):

#include <stdio.h>
void factorize_and_print(unsigned long number) {
  unsigned long factor;
  for(factor = 2; number > 1; factor++) {
    while(number % factor == 0) {
      number = number / factor;
      printf("%lu\n",factor);
    }
  }
}

/* example main */
int main(int argc,char** argv) {
  if(argc >= 2) {
    long number = atol(argv[1]);
    factorize_and_print(number);
  } else {
    printf("Usage: %s <number>%<number> is unsigned long", argv[0]);
  }
}

Примечание. Здесь есть ошибка разбора числа, которая не позволяет правильно получить число в argv.

Answer 5

Действительно, это очень медленно для всех, кроме самых маленьких чисел (скажем, ниже 100 000). Попробуйте найти только основные факторы числа:

#include <cmath>

void addfactor(int n) {
    printf ("%d\n", n);
}

int main()
{
    int d;
    int s;
    int c = 1234567;
    while (!(c&1)) {
        addfactor(2);
        c >>= 1;
    }
    while (c%3 == 0) {
        addfactor(3);
        c /= 3;
    }
    s = (int)sqrt(c + 0.5);
    for (d = 5; d <= s;) {
        while (c % d == 0) {
            addfactor(d);
            c /= d;
            s = (int)sqrt(c + 0.5);
        }
        d += 2;
        while (c % d == 0) {
            addfactor(d);
            c /= d;
            s = (int)sqrt(c + 0.5);
        }
        d += 4;
    }
    if (c > 1)
        addfactor(c);
    return 0;
}

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

Это значительно быстрее, чем другие фрагменты кода, размещенные здесь. Для случайного ввода, такого как 10597959011, мой код потребовал бы что-то вроде 2000-битных операций плюс еще 1000 для воссоздания делителей, в то время как другие потребовали бы миллиарды операций. В этом случае разница между «мгновенным» и минутным.