C Language Classic Example 14-Decompose a positive integer to a prime factor

1 Question

Decompose a positive integer to the prime factor. For example: input$90$, print it out$90=2\ast 3\ast 3\ast 5$

2 Analysis

The idea of ​​decomposing the prime factor is to use this numbernContinuously divided by an incremental numberi(The number is initially2, increment ton) If it can be removedi, then the current one isiJust fornone of the factors, thennUse this factor to narrow it, i.e.n=n/iRepeat the above operation ifn = iThis means that the decomposition factor is over

3 Implementation

#include <>

int main() {
	int n ;
	printf("Please enter a positive integer:");
	scanf("%d", &n);
	printf("%d = ", n);
	for (int i = 2; i <= n; i++) {
		while(n != i) { // The execution conditions must be different from n and i. If they are equal, the decomposition will be completed.
			if(n % i == 0) { // If the difference can be done, i is one of the factors that n
				printf("%d * ", i); // Output factor
				n = n / i; // A factor i is found, then n/i shrinks n and continues to search
			} else {
				break; // If you cannot separate it, you will jump out of this cycle and increment i to proceed to the next round
            }
		}
	}
	printf("%d\n", n); // The last remaining n cannot be divided into i, so it is also one of the factors, so the final output is
	return 0;
}

4 Running results

Please enter a positive integer:120
120 = 2 * 2 * 2 * 3 * 5