首页 > 代码库 > [BASIC-16] 分解质因数
[BASIC-16] 分解质因数
基础练习 分解质因数
时间限制:1.0s 内存限制:512.0MB
问题描述
求出区间[a,b]中所有整数的质因数分解。
输入格式
输入两个整数a,b。
输出格式
每行输出一个数的分解,形如k=a1*a2*a3...(a1<=a2<=a3...,k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5
提示
先筛出所有素数,然后再分解。
数据规模和约定
2<=a<=b<=10000
1、如提示所言,先筛出所有素数,然后再分解。
2、“筛法求素数”的思想及方法,可以参看我的另外一篇博客:http://blog.csdn.net/u011506951/article/details/26146595
import java.util.Scanner; public class Main { static final int CONSTANT = 10000; static final int[] ARRAY = new int[CONSTANT + 1]; static int[] primes = new int[1229]; static { createPrimes(); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int a = scanner.nextInt(); int b = scanner.nextInt(); primeFactors(a, b); } } private static void primeFactors(int a, int b) { for (; a <= b; a++) { int temp = a; System.out.print(a + "="); int i = 0; while (temp != 1) { if (temp % primes[i] == 0) { temp /= primes[i]; System.out.print(primes[i]); System.out.print(temp == 1 ? "\r\n" : "*"); } else { i++; } } } } private static void createPrimes() { for (int i = 2; i <= CONSTANT; i++) { if (ARRAY[i] == 0) { for (int j = i * 2; j <= CONSTANT; j += i) { ARRAY[j] = 1; } } } int k = 0; for (int i = 2; i <= CONSTANT; i++) { if (ARRAY[i] == 0) { primes[k++] = i; } } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。