output related to primes

Question

Only the function is written below

Function of prime factors

void prime(int x) {
    int i, j;             

wrote this because it wanted for information but don't have any

    for (i = 2; i <= x; i++) {
        if (x % i == 0) {
            for (j = 2; j <= i; j++) {
                if (i == j) {
                    printf("%d", i);
                } else
                if ((i % j) != 0) {
                    printf("%d\n", i);

The output should be prime numbers of the number and the repeated prime no.s also should be seen so by mutiplication we get the original number

                    goto l;

Here the goto statement takes out of if loop

                } else {
                    break;
                }
            }
        l: 
            x = x / i;
        }
    }
}

Code seems to be correct and also is giving the prime numbers but is the factors are not repeating itself.

for e.g: 24 output should be 2,2,3 but the output is coming as 2,3

Answer 1

My solution. I can add comments if you needed.

#include <stdio.h>

void prime_factors(int num) {
    int i = 2;
    while(num > 1) {
        while(num % i == 0) {
            num /= i;   
            printf("%d ", i); 
        }   
        i++;
    }   
}

int main() {
    int num;

    while(1) {
        printf("%s", "Enter the number: ");

        if(scanf("%d", &num) != 1)  
            break;

        // \033[1;31m - changes text color to red
        // \033[0;0m  - resets color back to default
        // It works on Linux, I don't know about Windows.
        if(num <= 1) {
            puts("\033[1;31mThe number must be greater than 1.\033[0;0m");
            continue;
        }   
        puts("Prime factors are:");

        prime_factors(num);

        puts("\n");
    }   

    return 0;
}

Testing:

Enter the number: 24
Prime factors are:
2 2 2 3 

Enter the number: 12
Prime factors are:
2 2 3 

Enter the number: 1000
Prime factors are:
2 2 2 5 5 5

Answer 2

The goto statement is useless, it is exactly equivalent to a break statement in your case. It does not break out of the if loop, it breaks out of the for loop, which is exactly what break does.

Furthermore, the inner loop is useless: if you divide x by i, you effectively remove the smaller primes from x, and x % i == 0 will hold only for prime values of i.

The problem in the output comes from the fact that you increment i even if x is a multiple of i. Therefore you only print a prime factor once and you do not remove it completely from x.

The function can thus be simplified into:

void primefactors(int x) {
    int i;             

    for (i = 2; i <= x;) {
        if (x % i == 0) {
            printf(" %d", i);
            x = x / i;
        } else {
            i++;
        }
    }
    printf("\n");
}

The function can be made much faster: you can stop the scan when i is greater than the square root of x:

void primefactors(int x) {
    int i;             

    for (i = 2; i * i <= x;) {
        if (x % i == 0) {
            printf(" %d", i);
            x = x / i;
        } else {
            i += 1 + (i & 1);  // skip even numbers
        }
    }
    printf("%d\n", x);
}