Integer факторизации в языке C

Question

Я делаю программу в C, чтобы сделать вывод выглядеть следующим образом:

2 = 2 
3 = 3 
4 = 2 x 2 
5 = 5 
6 = 2 x 3 
.... 
102 = 2 x 3 x 17 
103 = 103 
104 = 2 x 2 x 2 x 13 

Я написал код целое факторизации следующим образом:

#include <stdio.h> 
#define MAXNUM 1000 

int main(){ 
int num,numfordiv; 
int div = 2; 
for (num=2;num<MAXNUM;num++){ 
    printf("%d=", num); 
    numfordiv = num; 
    if(num%div != 0){ 
     div = div+1; 
    } 
    else{ 
     numfordiv = numfordiv/div; 
     printf("%d x ",div); 
     if(numfordiv == 1){ 
      div = 2; 
     } 
    } 
} 
return 0; 
} 

Однако, это не работает по неизвестной причине. Что-то не так с петлей?

Answer 1

Что вы можете сделать, чтобы генерировать выходной сигнал с просьбой, по крайней мере,

#include <stdio.h> 
#define MAXNUM 1000 

int main() 
{ 
    int num,numfordiv; 
    int div = 2; 
    for (num=2;num<MAXNUM;num++) 
    { 
     printf("%d= ", num); 
     numfordiv = num; 

     div = 2; 

     while (numfordiv>1) 
     { 
      if(numfordiv%div != 0) 
      { 
       div++; 
      } 
      else 
      { 
       numfordiv /= div; 
       printf("%d ",div); 
       if(numfordiv != 1) 
       { 
        printf("x "); 
       } 
      } 
     } 
     printf("\n"); 
    } 
    return 0; 
} 

Как вы можете видеть, что вам нужно:

1. внутренний контур для петель на всех возможных делителей
2. Для каждого номера вы должны сбросить свой делитель
3. Операция по модулю должна выполняться на разделенном номере

Answer 2

Ответ на @LP приятный и понятный.

Однако, если производительность имеет значение, у него есть недостаток для очень высоких значений MAXNUM. Так как div просто увеличивается на единицу в цикле while, производительность будет плохой для высоких чисел, так как код проверяет большое количество div-значений, которые потерпят неудачу. Простой пример: Нет необходимости устанавливать div на 4, 6, 8, 10 и т. Д.

Ниже приведен пример, который будет работать лучше для высоких чисел. Цена - более сложный код и больше использования памяти.

Основная идея состоит в том, чтобы собирать простые числа при обнаружении и устанавливать только div в простые значения, чтобы код пропускал множество чисел, которые никогда не пройдут тест %.

#include <stdio.h> 
#include <stdlib.h> 

#define MAXNUM 200000000 
#define INCREASE_BY 1000 

int main() 
{ 
    // Make array for collecting primes 
    int primes_array_size = INCREASE_BY; 
    int *primes = malloc(primes_array_size * sizeof(int)); 
    if (primes == NULL) 
    { 
     printf("out of memory\n"); 
     return 0; 
    } 

    // Add 2 as the first prime 
    primes[0] = 2; 
    int num_primes = 1; 
    int prime_pos = 0; 

    int num,numfordiv; 
    int div = 2; 

    for (num=2;num<MAXNUM;num++) 
    { 
     div = primes[0]; 
     prime_pos = 0; 

     printf("%d = ", num); 
     numfordiv = num; 

     while(numfordiv>1) 
     { 
      if(numfordiv % div != 0) 
      { 
       // Goto next prime (if there are any) 
       ++prime_pos; 
       if (prime_pos < num_primes) 
       { 
        div = primes[prime_pos]; 
       } 
       else 
       { 
        // No more primes in the list 
        break; 
       } 
      } 
      else 
      { 
       numfordiv = numfordiv/div; 
       printf("%d",div); 
       if (numfordiv != 1) printf(" x "); 
      } 
     } 

     if (numfordiv != 1) 
     { 
      // Found new prime - add it 
      primes[num_primes] = num; 
      ++num_primes; 
      printf("%d",num); 

      if (num_primes == primes_array_size) 
      { 
       // Allocate more memory 
       primes_array_size = primes_array_size + INCREASE_BY; 
       int* tmp = realloc(primes, primes_array_size * sizeof(int)); 
       if (tmp == NULL) 
       { 
        printf("out of memory\n"); 
        free(primes); 
        return 0; 
       } 
       primes = tmp; 
      } 

     } 

     printf("\n"); 
    } 

    free(primes); 
    return 0; 
}