黑马程序员技术交流社区

标题: 怎么将一个正整数分解质因数 [打印本页]

---

作者: 张龙跃    时间: 2013-5-16 20:56
标题: 怎么将一个正整数分解质因数


将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：
(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。
(2)如果n <>k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你n,重复执行第一步。
(3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。


import java.util.Scanner;

public class Hello {


        public static void main(String[] args) {
                Scanner input=new Scanner(System.in);
                System.out.println("请输入一个正整数");
                int a =input.nextInt();
               

        }

}

求思路

---

作者: 曾大鹏    时间: 2013-5-16 21:18
这题目以前搞acm写过，，发个c写的代码

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include <math.h>
   
4. #define MAX 40000
   
5. struct node
   
6. {
   
7.         int x,y;
   
8. }s[40000];
   
9. int a[MAX];
   
10. void prime()
    
11. {
    
12.         int i,j;
    
13.         memset(a,0,sizeof(a));
    
14.         for(i=2;i<=MAX;i++)
    
15.         {
    
16.                 if(a[i]==0)
    
17.                 {
    
18.                         for(j=2;j*i<=32000;j++)
    
19.                                 a[i*j]=1;//不是素数标记为1
    
20.                 }
    
21.         }
    
22. }
    
23. int main()
    
24. {
    
25.         int n,i,j,k,num;
    
26.         prime();
    
27.         while(scanf("%d",&n)!=EOF)
    
28.         {
    
29.                 k=sqrt(n);num=0;
    
30.                 if(n==1)
    
31.                 {
    
32.                         printf("1 = 1\n");
    
33.                         continue;
    
34.                 }
    
35.                 printf("%d = ",n);
    
36.                 for(i=2;i<=k;i++)
    
37.                 {
    
38.                         if(n%i==0&&a[i]==0)
    
39.                         {
    
40.                                 j=1;
    
41.                                 while(1)
    
42.                                 {
    
43.                                         n=n/i;
    
44.                                         if(n%i)
    
45.                                                 break;
    
46.                                         j++;
    
47.                                 }
    
48.                                 s[num].x=i;
    
49.                                 s[num++].y=j;
    
50.                                 k=sqrt(n);
    
51.                         }
    
52.                 }
    
53.                 if(n!=1)
    
54.                 {
    
55.                         s[num].x=n;
    
56.                         s[num++].y=1;
    
57.                 }
    
58.                 for(i=0;i<num;i++)
    
59.                 {
    
60.                         if(i==0)
    
61.                         {
    
62.                                 if(s[i].y==1)
    
63.                                         printf("%d",s[i].x);
    
64.                                 else
    
65.                                         printf("%d^%d",s[i].x,s[i].y);
    
66.                         }
    
67.                         else
    
68.                         {
    
69.                                 if(s[i].y==1)
    
70.                                         printf(" * %d",s[i].x);
    
71.                                 else
    
72.                                         printf(" * %d^%d",s[i].x,s[i].y);
    
73.                         }
    
74.                 }
    
75.                 printf("\n");
    
76.         }
    
77.         return 0;
    
78. }
    

复制代码

---

作者: 曾大鹏    时间: 2013-5-16 21:18
这题目以前搞acm写过，，发个c写的代码

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include <math.h>
   
4. #define MAX 40000
   
5. struct node
   
6. {
   
7.         int x,y;
   
8. }s[40000];
   
9. int a[MAX];
   
10. void prime()
    
11. {
    
12.         int i,j;
    
13.         memset(a,0,sizeof(a));
    
14.         for(i=2;i<=MAX;i++)
    
15.         {
    
16.                 if(a[i]==0)
    
17.                 {
    
18.                         for(j=2;j*i<=32000;j++)
    
19.                                 a[i*j]=1;//不是素数标记为1
    
20.                 }
    
21.         }
    
22. }
    
23. int main()
    
24. {
    
25.         int n,i,j,k,num;
    
26.         prime();
    
27.         while(scanf("%d",&n)!=EOF)
    
28.         {
    
29.                 k=sqrt(n);num=0;
    
30.                 if(n==1)
    
31.                 {
    
32.                         printf("1 = 1\n");
    
33.                         continue;
    
34.                 }
    
35.                 printf("%d = ",n);
    
36.                 for(i=2;i<=k;i++)
    
37.                 {
    
38.                         if(n%i==0&&a[i]==0)
    
39.                         {
    
40.                                 j=1;
    
41.                                 while(1)
    
42.                                 {
    
43.                                         n=n/i;
    
44.                                         if(n%i)
    
45.                                                 break;
    
46.                                         j++;
    
47.                                 }
    
48.                                 s[num].x=i;
    
49.                                 s[num++].y=j;
    
50.                                 k=sqrt(n);
    
51.                         }
    
52.                 }
    
53.                 if(n!=1)
    
54.                 {
    
55.                         s[num].x=n;
    
56.                         s[num++].y=1;
    
57.                 }
    
58.                 for(i=0;i<num;i++)
    
59.                 {
    
60.                         if(i==0)
    
61.                         {
    
62.                                 if(s[i].y==1)
    
63.                                         printf("%d",s[i].x);
    
64.                                 else
    
65.                                         printf("%d^%d",s[i].x,s[i].y);
    
66.                         }
    
67.                         else
    
68.                         {
    
69.                                 if(s[i].y==1)
    
70.                                         printf(" * %d",s[i].x);
    
71.                                 else
    
72.                                         printf(" * %d^%d",s[i].x,s[i].y);
    
73.                         }
    
74.                 }
    
75.                 printf("\n");
    
76.         }
    
77.         return 0;
    
78. }
    

复制代码

---

作者: 萌小子    时间: 2013-5-16 22:02

1. import java.util.Scanner;
   
2. 
   
3. public class QiuYinShu {
   
4. 
   
5. /**
   
6. * 将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
   
7. * 程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：
   
8. * (1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。
   
9. * (2)如果n <>k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数n,重复执行第一步。
   
10. * (3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。
    
11. * @param args
    
12. */
    
13. public static void main(String[] args) {
    
14. Scanner s=new Scanner(System.in);
    
15. System.out.println("请输入一个正整数");
    
16. int num=s.nextInt();
    
17. int k = 2;
    
18. System.out.print(num + "=");
    
19. while (num > k) {
    
20. if (num % k == 0) {
    
21. System.out.print(k + "*");
    
22. num = num / k;
    
23. }
    
24. if (num % k != 0) {
    
25. k++;
    
26. }
    
27. }
    
28. System.out.println(k);
    
29. }
    
30. }
    

复制代码

---

作者: Sword    时间: 2013-5-17 00:19

曾大鹏 发表于 2013-5-16 21:18
这题目以前搞acm写过，，发个c写的代码

恩恩，不错。不过最好用java写代码

---

作者: 逸盏清茶    时间: 2013-5-17 00:43
public static void main(String[] args)
        {
                int n,i;
                Scanner input=new Scanner(System.in);
        System.out.println("请输入一个正整数");
        n =input.nextInt();
        for(i=2;i<=n;i++)
            {
                while(n!=i)
                {
                        if(n%i==0)
                        {
                                System.out.println(i);
                                n=n/i;
                        }
                        else
                                break;
                }
        }
        System.out.println(n);
               
        }

---

作者: 飞鸟青崖    时间: 2013-5-17 08:59
这道题通过递归的方法比较好求。
1，首先求出任意一个数的约数，这样就将这个数分成了两个数。
2，然后对这两个数求取质因数。这样递归下去就可以解决了。
下面是代码。不过没有考虑格式，只是把结果给直接输出来了。

1. import java.util.Scanner;
   
2. 
   
3. 
   
4. class MyTest{
   
5.          public static void main(String[] args) {
   
6.                  Scanner sc = new Scanner(System.in);
   
7.                  int num = sc.nextInt();
   
8.                  getPrime(num);
   
9.                  
   
10.          }
    
11.          //获得一个数的约数。如果它本身但是一个素数，那么就返回它本身。
    
12.          private static int getAppro(int n){
    
13.                  for(int x=2;x<=Math.sqrt(n);x++){
    
14.                          if(n%x == 0){
    
15.                                  return x;
    
16.                          }
    
17.                  }
    
18.                  return n;
    
19.          }
    
20.          //求一个数的质因数。
    
21.          private static void getPrime(int n){
    
22.                  if(n != getAppro(n)){//如果它本身不是素数，就将它分成两部分。
    
23.                          getPrime(n/getAppro(n));
    
24.                          getPrime(getAppro(n));
    
25.                  }
    
26.                  else//如果它是素数，就直接输出这个数。
    
27.                          System.out.println(n);
    
28.          }
    
29. }                 

复制代码

---

作者: 曾大鹏    时间: 2013-5-17 09:02

王盟盟 发表于 2013-5-16 22:02

你这效率有问题的 如果这个N很大的话 你的程序出结果的时间会很慢的。。
应该考虑用刷选法把素数找出来的。。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2