HDU 1164 Eddy's research I（ 试除法 & 筛法改造试除法 分解整数 ）
2024-08-30 19:13:52
**链接：****传送门 **
题意：给出一个整数 n ，输出整数 n 的分解成若干个素因子的方案
思路：经典的整数分解题目，这里采用试除法 和 用筛法改造后的试除法 对正整数 n 进行分解
方法一：试除法对正整数 n 进行分解
/*************************************************************************
> File Name: hdu1164.cpp
> Author: WArobot
> Blog: http://www.cnblogs.com/WArobot/
> Created Time: 2017年05月23日 星期二 22时40分34秒
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
vector<int> fac[65536];
void init(){
for(int x = 1 ; x <= 65535 ; x++){
int tmp = x , cnt = 0;
for(int i = 2 ; i*i <= tmp ; i++){
while ( tmp % i == 0 ){
fac[x].push_back(i);
tmp /= i;
}
}
if( tmp != 1 ) fac[x].push_back(tmp);
}
}
int main(){
init();
int n;
while(~scanf("%d",&n)){
int len = fac[n].size();
for(int i = 0 ; i < len - 1 ; i++)
printf("%d*",fac[n][i]);
printf("%d\n",fac[n][len-1]);
}
return 0;
}
方法二：筛法对试除法进行优化
原理：相较以试除法不经挑选跑遍整个 [ 1 , sqrt(n) ] ，其中 i = 合数的时候实际上是无效的操作，不如直接打出素数表，跑一下素数表来避免判断大量的合数情况来加速
/*************************************************************************
> File Name: hdu1164t2.cpp
> Author: WArobot
> Blog: http://www.cnblogs.com/WArobot/
> Created Time: 2017年05月23日 星期二 23时06分28秒
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 65535 + 10;
vector<int> fac[MAX_N];
int prime[MAX_N] = {0} , pri_list[MAX_N] , pri_cnt = 0;
void init_prime(){
for(int i = 2 ; i*i < MAX_N ; i++){
if( prime[i] == 0 ){
pri_list[ pri_cnt++ ] = i;
for(int j = 2*i ; j < MAX_N ; j += i) prime[i] = 1;
}
}
}
void init_ans_list(){
for(int x = 1 ; x < MAX_N ; x++){
int tmp = x , cnt = 0;
for(int i = 0 ; pri_list[i] <= tmp && i < pri_cnt ; i++){
while( tmp % pri_list[i] == 0 ){
fac[x].push_back(pri_list[i]);
tmp /= pri_list[i];
}
}
if( tmp != 1 ) fac[x].push_back(tmp);
}
}
int main(){
init_prime();
init_ans_list();
int n;
while(~scanf("%d",&n)){
int len = fac[n].size();
for(int i = 0 ; i < len-1 ; i++) printf("%d*",fac[n][i]);
printf("%d\n",fac[n][len-1]);
}
return 0;
}最新文章
- 我叫Twenty，我是要成为博客王的博客框架
- C语言中结构体赋值问题的讨论
- vs默认VS Development Sever和用IIS Web Server的一点差别
- VS2010项目的部署与安装
- Intel 凌动 D525 产品参数Intel 凌动 Z3735F 产品参数
- 基于visual Studio2013解决C语言竞赛题之0604二维数组置换
- Source Insight使用技巧
- （转）Windows7下命令行使用MySQL
- SSM项目使用GoEasy 实现web消息推送服务
- oracle中 特殊字符 转义 （&）
- 状态压缩dp小结
- flask-admin fileadmin 上传文件，中文名的解决方案 重写部分secure_filename
- PostgreSQL的目录结构及修改数据目录
- 利用Chrome浏览器的开发者工具截取整个页面
- buildroot 搭建ftpd 服务器记录
- webapi views目录下html文件无法访问
- 【洛谷】P2694 接金币（排序）
- c++ reference can not be reassigned
- hdu 5188(带限制的01背包)
- 13.1Springboot 之 静态资源路径配置