Brush questions - Luogu -p1075 prime factor decomposition

P1075 Prime factor decomposition -C Language

1、 subject

2、 The problem solving process

(1) for the first time Because of the timeout Write too many cycles In particular, bubble sorting is not necessary
result ：

Code ：

(2) The second time Removed bubble sort But it's still overtime
Code :

// Luogu  P1075  Prime factor decomposition 
#include <stdio.h>
#define MAX 200
int main() {
    
	int n;// Positive integer  1<=n<=2*10 Of 9 Power 
	int factor[MAX];// Factor 
	int prime[MAX];// Prime number 
	int i, j, k;
	int temp;// Bubble sort temporary value 
	int counter = 0;// Counter   Number of counting factors 
	scanf("%d", &n);// Enter a positive integer n
	// Factor 
	for (i = 1; i <= n; i++) {
    
		if (n % i == 0) {
    
			factor[counter] = i;

			counter++;
			//printf("%d", i);// Factor 
		}
	}
	k = 0;// Prime subscript 
	// Find prime number 
	for (i = 0; i < counter; i++) {
    // Number of factors to be processed circularly 
		for (j = 2; j < factor[i]; j++) {
    
			if (factor[i] % j == 0) {
    // Not prime 
				break;
			}
		}
		if (j >= factor[i]) {
    // Print prime 
			prime[k] = factor[i];
			k++;
			//printf("\n %d ", factor[i]);
		}
	}
	//printf(" Maximum ：%d",prime[k] );
	printf("%d", prime[k-1]);

	return 0;
}

(3) third time What is special about this problem is that it is set as a positive integer N Is the product of two different prime numbers .
result ：

Code ：

// Luogu  P1075  Prime factor decomposition 
#include <stdio.h>
int main() {
    
	int n;// Positive integer  1<=n<=2*10 Of 9 Power 
	int i;
	scanf("%d", &n);// Enter a positive integer n
	if (n == 1 || n==2 || n==3) {
    
		printf("%d", n );
		return 0;
	}
	// Find the quality factor 
	for (i = 2; i <= n; i++) {
    
		if (n % i == 0) {
    
			
			printf("%d", n/i);// Factor 
			break;
		}
	}

	return 0;
}