Поиск наибольшего простого множителя составного числа в 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

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

Answer 2

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

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

Answer 3

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

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

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

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/делителя. Мы можем использовать подход 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 4

Действительно, это очень медленно, для всех, кроме самых маленьких номеров (ниже, скажем, 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, чтобы повторно составлять дивизоры, а другие - миллиарды операций. В этом случае разница между «мгновением» и минутой.

Answer 5

Облегчение ответить 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 правильно.