[编程题]分解因数
- 热度指数：9196 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
所谓因子分解，就是把给定的正整数a，分解成若干个素数的乘积，即 a = a1 × a2 × a3 × ... × an,并且 1 < a1
≤ a2 ≤ a3 ≤ ... ≤ an。其中a1、a2、...、an均为素数。 先给出一个整数a，请输出分解后的因子。
输入描述:
输入包含多组数据，每组数据包含一个正整数a（2≤a≤1000000）。
输出描述:
对应每组数据，以“a = a1 * a2 * a3...”的形式输出因式分解后的结果。
示例1
输入
10<br/>18
输出
10 = 2 * 5<br/>18 = 2 * 3 * 3
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int num;
while (cin >> num)
{
cout << num << " = ";
int* num1 = new int[1000];
int j = 0;
for (int i = 2; i <= sqrt(num); i++)
{
while (num % i == 0)
{
if (num != 1)
{
num1[j] = i;
j++;
num /= i;
}
}
}
if (num != 1)
{
num1[j] = num;
j++;
}
for (int k = 0; k < j; k++)
{
cout << num1[k];
if (k + 1 < j)
{
cout << " * ";
}
}
cout << endl;
}
return 0;
}
发表于 2019-07-08 21:33:11
回复(0)
详细解释：
https://blog.csdn.net/qq_33375598/article/details/104605087
#include <cstdio>
(802)#include <cmath>
struct factor{
int x;
int cnt;
}fac[10];
const int MAXN = 100010;
int prime[MAXN], pNum = 0;
bool p[MAXN] = {false};
void findPrime(){
for (int i = 2; i < MAXN; ++i) {
if(p[i] == false){
prime[pNum++] = i;
for (int j = i + i; j < MAXN; j += i) {
p[j] = true;
}
}
}
}
int main(int argc, char const *argv[]){
findPrime();
int n;
while(scanf("%d", &n) != EOF){
int N = n;
int num = 0;//不同质因子的个数
int sqr = (int)sqrt(n*1.0);
for (int i = 0; i < pNum && prime[i] <= sqr; ++i) {
if(n % prime[i] == 0){//如果prime[i]是n的质因子
fac[num].x = prime[i];
fac[num].cnt = 0;
while(n % prime[i] == 0){//计算质因子prime[i]个数
fac[num].cnt++;
n /= prime[i];
}
num++;//不同的质因子个数加1
}
if(n == 1) break;
}
if(n != 1){
fac[num].x = n;
fac[num++].cnt = 1;
}
printf("%d = ", N);
int count = 0;//统计是否是一个乘数，如果不是则打印*
for (int j = 0; j < num; ++j) {
while(fac[j].cnt > 0){
if(count != 0) printf(" * ");
printf("%d", fac[j].x);
fac[j].cnt--;
count++;
}
}
printf("\n");
}
return 0;
}
发表于 2020-03-02 09:09:33
回复(1)
/*暴力。。。试探*/
#include <iostream>
using namespace std;
int main()
{
int a = 0, i = 0;
while (cin >> a)
{
cout << a << " = ";
i = 2;
while (1) //找到第一个可以整除的素数，为了格式的操作
{
if (a % i == 0)
{
cout << i;
a = a / i;
break;
}
i++;
}
while (a != 1) //找到剩余可以整除的素数
{
i = 2;
while(1)
{
if (a % i == 0)
{
cout << " * " << i;
a = a / i; //a一直在不断地减小
break;
}
i++;
}
}
cout << endl;
}
return 0;
}
发表于 2018-08-16 20:40:41
回复(0)
思路：生成列表然后比对输出。
#include <iostream>
using namespace std;
#define N 1000000
int prime[1000001];
void init() {
int i, j;
for (i = 2; i <= N; i++) {
prime[i] = 1;
}
for (i = 2; i <= N; i++) {
//if (prime[i]) printf(" %d ", i);
for (j = i + i; j <= N; j += i) prime[j] = 0;
}
}
int main()
{
int n;
init();
while (cin >> n)
{
cout << n << " = ";
if (prime[n] == 1)
{
cout << n << endl;
continue;
}
for (int j = 2; j <= n;)
{
if (prime[j] == 0)
{
j++;
continue;
}
if (n % j == 0 && (n/j) != 1)
{
cout << j << " * ";
n = n / j;
}
else if (n % j == 0 && (n / j) == 1)
{
cout << j << endl;
n = n / j;
break;
}
else
{
j++;
}
}
}
}
发表于 2018-08-12 10:41:46
回复(0)
#include<iostream>
#include<cstdio>
#include<memory.h>
#include<string>
#include<cmath>
using namespace std;
int gcd(int a,int b){
if(b == 0){
return a;
}
return gcd(b,a%b);
}
int main(void){
int a,b,c,d,temp;
char ch;
while(scanf("%d/%d %d/%d
%c",&a,&b,&c,&d,&ch) != EOF){
switch(ch){
case '+':
a *= d;
c *= b;
a += c;
b *= d;
break;
case '-':
a *= d;
c *= b;
a -= c;
b *= d;
break;
case '*':
a *= c;
b *= d;
break;
case '/':
a *= d;
b *= c;
break;
}
temp = gcd(a,b);
a /= temp;
b /= temp;
if(a*b < 0){
a = -abs(a);
b = abs(b);
}
printf("%d/%d\n",a,b);
}
}
发表于 2015-07-06 21:11:59
回复(1)
#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
int A[78500];
int prim(){
int index=0,i;
vector<bool> b(1000000,false);
for(i=2;i<1000000;i++){
if(!b[i]){
A[index++]=i;
}
for(int j=2*i;j<1000000;j+=i){
b[j]=true;
}
}
return index;
}
int main(){
int index=prim();
int n;
while(scanf("%d",&n)!=EOF){
printf("%d = ",n);
while(n!=1){
for(int i=0;n!=1&&i<index;i++){
if(n%A[i]==0){
while(n%A[i]==0){
n/=A[i];
if(n!=1){
printf("%d * ",A[i]);
}
else{
printf("%d",A[i]);
printf("\n");
}
}
}
}
}
}
return 0;
}
发表于 2015-11-20 16:15:31
回复(1)
#include<stdio.h>
int main()
{
int x, pri[] = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997 };
while (~scanf("%d", &x))
{
printf("%d = ",x);
for (int i = 0;i < 168;i++)
{
if (x <= pri[i])
{
printf("%d\n", x);
break;
}
while (x%pri[i] == 0 && x > pri[i])
{
printf("%d * ", pri[i]);
if (x%pri[i] == 0)
x /= pri[i];
}
}
if (x > 997)
printf("%d\n", x);
}
return 0;
}
发表于 2017-08-04 13:57:39
回复(5)
90 = 2 * 3 * 3 * 5
要想求出它的每一个质因数，我们需要用质数去试除。90能被2整除，那就拿商继续除以2，除不尽就换3，一直到除到质数为止。基础代码框架类似判断质数，只是被判断的数字在过程中不断被除，最终循环结束的时候，那个被处理过的数字，就是最后一个质因数。 #include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
while(cin >> n){
cout << n << " = ";
for(int i = 2; i <= sqrt(n); ++i){
//反复除同一个数，直到除不尽，排除刚好是该数的n次方的情况
while(n % i == 0 && n != i){
cout << i << " * ";
n /= i;//能整除就修改n的值
}
}
cout << n << endl;
}
return 0;
}
发表于 2020-07-18 11:36:59
回复(0)
不用列出素数表！若n是合数，其中一个因数一定要<=sqrt(n),从i=2遍历到sqrt(n)就可以了
#include<stdio.h>
#include<math.h>
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF)
{
printf("%d = ",n);
for (i=2;i<=sqrt(n);i++)
{
while(n!=i)
{
if(n%i==0)
{
printf("%d * ",i);
n=n/i;
}
else break;
}
}
printf("%d\n",n); //这个时候最后一个因素i刚好等于n
}
return 0;
}
发表于 2017-05-13 20:48:58
回复(0)
import java.util.Scanner;
/*
* 分解因数
*/
//用质数去试除。90能被2整除，那就拿商继续除以2，除不尽就换3，一直到除到质数为止。
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int num = sc.nextInt();
System.out.print(num + " = ");
for (int i = 2; i <= num; i++) {
while (num % i == 0) {
if (num == i) {
System.out.println(i);
} else {
System.out.print(i + " * ");
}
num /= i;
}
}
}
}
}
发表于 2023-04-10 17:23:05
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int tmp = in.nextInt();
int i = 0;
System.out.print(tmp + " =");
while (tmp != 0) {
for (i = 2; i <= tmp; i++) {
if (tmp % i == 0) {
System.out.print(" " + i + " ");
if (tmp != i) {
System.out.print("*");
}
break;
}
}
tmp = tmp / i;
}
System.out.println();
}
}
}
发表于 2023-03-15 20:18:52
回复(0)
import java.util.*;
public class Main{
public static void getPrimeNum(ArrayList<Integer> list,int n){
for(int i = 2; i <= Math.sqrt(n); i++){
if(n % i == 0){
while(n % i == 0){
list.add(i);
n = n / i;
}
}
}
//素数的情况
if(n != 1){
list.add(n);
}
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
int a = scan.nextInt();
ArrayList<Integer> list = new ArrayList<>();
getPrimeNum(list,a);
System.out.printf("%d = ",a);
System.out.printf("%d",list.get(0));
for(int i = 1; i < list.size(); i++){
System.out.printf(" * %d",list.get(i));
}
System.out.println();
}
}
}
发表于 2023-02-14 14:40:18
回复(0)
// write your code here
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int a = sc.nextInt();
StringBuilder ans = new StringBuilder();
ans.append(a);
ans.append(" =");
for (int i = 2; i * i <= a; i++) {
if (a % i == 0) {
while (a % i == 0) {
ans.append(" ");
ans.append(i);
ans.append(" *");
a /= i;
}
}
}
if (a != 1) {
ans.append(" ");
ans.append(a);
} else {
ans.delete(ans.length()- 2, ans.length());
}
System.out.println(ans);
}
}
}
发表于 2022-09-30 18:59:10
回复(0)
import java.util.Scanner;
/**
* 分解因子
* @author haomin
* @date 2022/05/30 17:09
**/
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int numE = in.nextInt();
int num = numE;
// 创建一个字符串存储已找到的因子
int first = 0;
String str = "";
for (int i = 2; i <= num; i++) {
if(num % i == 0){
while (num % i == 0){
if(first == 0){
str += i;
first++;
}else {
str += " * ";
str += i;
}
num /= i;
}
}
}
System.out.println(numE +" = "+str);
}
}
}
发表于 2022-05-30 17:34:35
回复(0)
import java.util.*;
import java.math.*;
public class Main{
public static List<String> fun(int n){
List<String> list = new ArrayList<>();
for(int i = 2;i <= Math.sqrt(n);i++){
while(n % i == 0){
list.add(String.valueOf(i));
n /= i;
}
}
if(n != 1){
list.add(String.valueOf(n));
}
return list;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
List<String> list = fun(n);
System.out.printf("%d = %s\n",n,String.join(" * ",list));
}
}
}
发表于 2022-05-12 14:57:55
回复(3)
#include<stdio.h>
#include<math.h>
int main() {
int a, flag = 1;
while (scanf("%d", &a) != EOF) {
if (flag == 1) {
flag++;
printf("%d = ", a);
}
for (int i = 2; i <= a;) {
if (a % i == 0) {
if (flag == 2) {
printf("%d", i);
a = a / i;
flag++;
} else {
printf(" * %d", i);
a = a / i;
}
} else {
i++;
}
}
printf("\n");
flag = 1;
}
}
有大佬能帮我优化一下吗，569ms太久了，但是不会优化了
发表于 2022-04-18 22:36:39
回复(0)
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin >> n)
{
cout << n << " = ";
for(int i = 2; i * i <= n; i++)
{
while(n != i)
{
if(n % i == 0)
{
cout << i << " * ";
n /= i;
}
else
break;
}
}
cout << n << endl;
}
return 0;
}
发表于 2021-11-16 15:07:05
回复(0)
//不晓得为什么提交错误
#include <iostream>
#include<cmath>
using namespace std;
bool prime(int n)
{
int i;
bool yes = true;
for (i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)
{
yes = false;
break;
}
}
return yes;
}
int main()
{
int i, n;
while (cin >> i)
{
cout << i << "=";
for (n = 2; n < 1000; n++)
{
while (prime(n) && i % n == 0)
{
if (i / n == 1)
{
cout << n << endl;
break;
}
i = i / n;
cout << n << "*";
}
}
}
}
#include <iostream>
#include<cmath>
using namespace std;
bool prime(int n)
{
int i;
bool yes = true;
for (i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)
{
yes = false;
break;
}
}
return yes;
}
int main()
{
int i, n;
while (cin >> i)
{
cout << i << "=";
for (n = 2; n < 1000; n++)
{
while (prime(n) && i % n == 0)
{
if (i / n == 1)
{
cout << n << endl;
break;
}
i = i / n;
cout << n << "*";
}
}
}
}
发表于 2021-08-15 15:42:42
回复(0)
问题信息
难度：
48条回答
31收藏
11834浏览
通过挑战的用户
-
2023-03-14 19:58:39
-
2023-03-14 19:42:06
-
2023-03-14 18:55:01
-
2023-03-14 14:57:34
-
2023-03-14 09:44:41
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
