将一个数分解为素数的乘积并像 18=2*3^2 这样打印

Question

我必须编写一个程序，将数字分解为素数并打印成 18=2*3^2

#include <stdio.h>
void decompose(int n);
unsigned checkprime(int i);

int main() {
    printf("100=");
    decompose(100);
    printf("1\n");
    return 0;
}

void decompose(int n) {
    int i;
    for (i=2; n>1; ++i) {
        if (checkprime(i) == 1 && n%i == 0) {
           n /= i;
           printf("%d*", i);
           i=1;
        }
    }
}

unsigned checkprime(int i) {
   if (i==1)
      return 0;
    for (int j=2; j<=i/2; j++) {
        if (i%j == 0)
            return 0;
    }
    return 1;
}

我想不出任何正确打印它的方法

Answer 1

我们初学者应该互相帮助。:)

给你。

#include <stdio.h>

void decompose( unsigned int n )
{
    const unsigned int FIRST_PRIME = 2;

    printf( "%u = ", n );

    if ( n < FIRST_PRIME )
    {
        printf( "%u\n", n );
    }

    unsigned int m = FIRST_PRIME;

    while ( n > 1 )
    {
        unsigned int i = 0;

        while ( n % m == 0 )
        {
            ++i;
            n /= m;
        }

        if ( i != 0 )
        {
            printf( "%u", m );
            if ( i != 1 )
            {
                printf( "^%u", i );
            }

            if ( n != 1 ) putchar( '*' );
        }

        m = m == FIRST_PRIME ? 3 : m + 2;
    }
}


int main(void) 
{
    while ( 1 )
    {
        printf( "Enter a non-negative number (0 - exit): " );

        unsigned int n;

        if ( scanf( "%u", &n ) != 1 || n == 0 ) break;

        putchar( '\n' );
        decompose( n );
        putchar( '\n' );
    }

    return 0;
}

程序输出可能如下所示

Enter a non-negative number (0 - exit): 1

1 = 1

Enter a non-negative number (0 - exit): 2

2 = 2

Enter a non-negative number (0 - exit): 3

3 = 3

Enter a non-negative number (0 - exit): 4

4 = 2^2

Enter a non-negative number (0 - exit): 5

5 = 5

Enter a non-negative number (0 - exit): 6

6 = 2*3

Enter a non-negative number (0 - exit): 7

7 = 7

Enter a non-negative number (0 - exit): 8

8 = 2^3

Enter a non-negative number (0 - exit): 9

9 = 3^2

Enter a non-negative number (0 - exit): 10

10 = 2*5

Enter a non-negative number (0 - exit): 11

11 = 11

Enter a non-negative number (0 - exit): 12

12 = 2^2*3

Enter a non-negative number (0 - exit): 13

13 = 13

Enter a non-negative number (0 - exit): 14

14 = 2*7

Enter a non-negative number (0 - exit): 15

15 = 3*5

Enter a non-negative number (0 - exit): 16

16 = 2^4

Enter a non-negative number (0 - exit): 17

17 = 17

Enter a non-negative number (0 - exit): 18

18 = 2*3^2

Enter a non-negative number (0 - exit): 19

19 = 19

Enter a non-negative number (0 - exit): 20

20 = 2^2*5

Enter a non-negative number (0 - exit): 0

至于您的代码，例如甚至函数 checkprime 也是无效的。它 returns 1 至少对于数字 1 和 4 但这些数字不是素数。:)

unsigned checkprime (int i){

    for (int j=2;j<i/2;j++) {
        if(i%j==0)
        return 0;
    }
  return 1;
}

Answer 2

我建议您在 decompose 函数中进行以下两项优化：

void decompose(int n) {
    int first = 1;  // check if first prime factor

    while (n % 2 == 0) {
        n /= 2;
        if (first) {
            first = 0;
            printf("2");
        } else {
            printf("*2");
        }
    }
    // here, n must be odd

    int s = sqrt(n); // 1st optimization: 
    for (int i = 3; i <= s;) {
        if (checkprime(i) && n % i == 0) {
            n /= i;
            if (first) {
                first = 0;
                printf("%d", i);
            } else {
                printf("*%d", i);
            }
        } else {
             i += 2; // 2nd optimization: n must be odd
        }
    }
}

将一个数分解为素数的乘积并像 18=2*3^2 这样打印

Decompose a number to product of prime numbers and print it like 18=2*3^2

c

function

loops

primes

definition