欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

FOJ 1075 分解素因子

程序员文章站 2022-03-04 23:01:22
...

一,问题描述

FOJ 1075 分解素因子

       注意:输入一个测试用例后,第二行会立即输出这个测试用例的结果,并不是等所有测试用例都输入后,再一次性输出所有测试用例

 正确输入输出格式:

2

11

11

9828

2*2*3*3*3*7*13

二,问题分析

       问题的求解思路如下:首先把所有1到65535范围内的所有素数找出来,并用数组保存,对于每一个测试用例,依次用素数数组的元素从小到大比较,如果能够被整除,就输出该元素,注意输出的格式要求。

三,问题解答

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;


vector<int> sushu;						//1到65535之间的所有素数
int judge(int n) {
	int k = (int)sqrt((double)n);		//sqrt的参数类型为double
	for (int i = 2; i <= k; i++) {
		if (n % i == 0) {
			return 0;		//不是素数
		}
	}
	return 1;				//n是素数
	
}
void fun(vector<int>& vec) {				//存储素数数组
	for (int i = 2; i <= 65535; i++) {
		if (judge(i) == 1) {
			vec.push_back(i);
		}
		else {
			continue;
		}
	}
}


int main() {
	int num;			//测试样例个数
	fun(sushu);
	while (cin >> num) {
		for (int i = 0; i < num; i++) {
			int n;
			cin >> n;
			int k = 0;
			int flag = 0;				//用于控制输出格式
			while (sushu[k] <= n) {
				if (n % sushu[k]==0) {
					if (flag==0) {		//第一个只输出数字
						cout << sushu[k];
					}
					else {
						cout << "*" << sushu[k];
					}
					flag++;
					n = n / sushu[k];
				}
				else {
					k++;
				}
			}
			cout << endl;
		}
	}
	
	return 0;
}

 

相关标签: FOJ