蓝桥杯 基础练习 分解质因数（java）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了蓝桥杯 基础练习 分解质因数（java），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1721字，纯文字阅读大概需要3分钟。
内容图文
问题描述
求出区间[a,b]中所有整数的质因数分解。
输入格式
输入两个整数a，b。
输出格式
每行输出一个数的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=22
5=5
6=23
7=7
8=222
9=33
10=25
提示
先筛出所有素数，然后再分解。
数据规模和约定
2<=a<=b<=10000
刚开始， 因为我提交的代码只有60分，超时了，虽然及格了，而且我感觉没什么可以改进的地方了，但谁让我有强迫症呢，一堆正确里混入一个超时，，我很难受。。我就去百度，看有没有什么更好的思路，随便找了几份代码直接提交后发现全都超时了，有一个只有10分。可能是他们没有用蓝桥杯的联系系统？或者没有VIP？
看来只能靠自己了，经过一番辛苦，在整体思路不变的情况下，调整代码结构，硬是搞成100了。
好，下面来说我的思路：
最主要的是用了欧拉筛筛出素数，关于欧拉筛，可以看这篇：筛法求2到n的所有素数
代码整体是在欧拉筛的基础上改的，具体思路代码中有详细的注释。
贴上代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int a=scanner.nextInt();
int b=scanner.nextInt();
scanner.close();
boolean[] v=new boolean[b+1];
int[] prime=new int[b];
int pNum=0;
for (int i = 2; i <= b; i++) {
if (v[i]==false) {
prime[pNum++]=i;
}
int k=i;
for(int j=0;j<pNum;j++) {
if(i*prime[j] <= b&&i%prime[j]!=0) v[i*prime[j]]=true;
//此时prime中包括小于i的所有素数
//下面的代码是在欧拉筛的基础上新加的
if (i>=a) {
if (j==0) {//j=0说明是第一次
System.out.print(i+"=");
}
while (k%prime[j]==0) {//因为质因数会有重复出现的情况，如 8=2*2*2
if (k!=i) {
System.out.print("*");
}
System.out.print(prime[j]);
k=k/prime[j];
}//while执行完后，k中就含有prime[j]质因数，可以判断下一个素数了
if (k==1) {//k=1说明已除尽，质因数分解完成
System.out.println();
break;
}
}
}
}
}
}
内容总结
以上是互联网集市为您收集整理的蓝桥杯 基础练习 分解质因数（java）全部内容，希望文章能够帮你解决蓝桥杯 基础练习 分解质因数（java）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。