刷题-洛谷-P1075 质因数分解

P1075 质因数分解-C语言

1、题目

2、解题过程

(1)第一次 因为超时 写了太多的循环 特别是冒泡排序没必要
结果：

代码：

(2)第二次 去掉了冒泡排序 但还是超时
代码:

//洛谷 P1075 质因数分解
#include <stdio.h>
#define MAX 200
int main() {
    
	int n;//正整数 1<=n<=2*10的9次方
	int factor[MAX];//因数
	int prime[MAX];//质数
	int i, j, k;
	int temp;//冒泡排序临时值
	int counter = 0;//计数器 计因数个数
	scanf("%d", &n);//输入正整数n
	//求因数
	for (i = 1; i <= n; i++) {
    
		if (n % i == 0) {
    
			factor[counter] = i;

			counter++;
			//printf("%d", i);//因数
		}
	}
	k = 0;//质数下标
	//求质数
	for (i = 0; i < counter; i++) {
    //要循环处理的因数个数
		for (j = 2; j < factor[i]; j++) {
    
			if (factor[i] % j == 0) {
    //不是质数
				break;
			}
		}
		if (j >= factor[i]) {
    //打印质数
			prime[k] = factor[i];
			k++;
			//printf("\n %d ", factor[i]);
		}
	}
	//printf("最大值：%d",prime[k] );
	printf("%d", prime[k-1]);

	return 0;
}

(3)第三次 这道题比较特别的就是题设中正整数N是两个不同质数的乘积。
结果：

代码：

//洛谷 P1075 质因数分解
#include <stdio.h>
int main() {
    
	int n;//正整数 1<=n<=2*10的9次方
	int i;
	scanf("%d", &n);//输入正整数n
	if (n == 1 || n==2 || n==3) {
    
		printf("%d", n );
		return 0;
	}
	//求质因数
	for (i = 2; i <= n; i++) {
    
		if (n % i == 0) {
    
			
			printf("%d", n/i);//因数
			break;
		}
	}

	return 0;
}