A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 张龙跃 中级黑马   /  2013-5-16 20:56  /  2872 人查看  /  7 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 张龙跃 于 2013-5-16 20:59 编辑

将一个正整数分解质因数。例如:输入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();
               

        }

}

求思路

评分

参与人数 1技术分 +1 收起 理由
Sword + 1

查看全部评分

7 个回复

倒序浏览
这题目以前搞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. }
复制代码
回复 使用道具 举报
这题目以前搞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. }
复制代码
回复 使用道具 举报
  1. import java.util.Scanner;

  2. public class QiuYinShu {

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

评分

参与人数 1技术分 +1 收起 理由
Sword + 1

查看全部评分

回复 使用道具 举报
曾大鹏 发表于 2013-5-16 21:18
这题目以前搞acm写过,,发个c写的代码

恩恩,不错。不过最好用java写代码
回复 使用道具 举报
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);
               
        }
回复 使用道具 举报
这道题通过递归的方法比较好求。
1,首先求出任意一个数的约数,这样就将这个数分成了两个数。
2,然后对这两个数求取质因数。这样递归下去就可以解决了。
下面是代码。不过没有考虑格式,只是把结果给直接输出来了。
  1. import java.util.Scanner;


  2. class MyTest{
  3.          public static void main(String[] args) {
  4.                  Scanner sc = new Scanner(System.in);
  5.                  int num = sc.nextInt();
  6.                  getPrime(num);
  7.                  
  8.          }
  9.          //获得一个数的约数。如果它本身但是一个素数,那么就返回它本身。
  10.          private static int getAppro(int n){
  11.                  for(int x=2;x<=Math.sqrt(n);x++){
  12.                          if(n%x == 0){
  13.                                  return x;
  14.                          }
  15.                  }
  16.                  return n;
  17.          }
  18.          //求一个数的质因数。
  19.          private static void getPrime(int n){
  20.                  if(n != getAppro(n)){//如果它本身不是素数,就将它分成两部分。
  21.                          getPrime(n/getAppro(n));
  22.                          getPrime(getAppro(n));
  23.                  }
  24.                  else//如果它是素数,就直接输出这个数。
  25.                          System.out.println(n);
  26.          }
  27. }                 
复制代码
回复 使用道具 举报
王盟盟 发表于 2013-5-16 22:02

你这效率有问题的 如果这个N很大的话 你的程序出结果的时间会很慢的。。
应该考虑用刷选法把素数找出来的。。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马