华师一附中OI组

标题: 分解质因数 [打印本页]
作者: admin    时间: 2018-7-23 09:51
标题: 分解质因数
输入一个自然数分解质因数，比如100=2*2*5*5。
此题考查对循环的理解，要认真思考。
作者: walk_alone    时间: 2018-7-23 18:49
  1. #include <cstdio>
  2. int judge(int x)
  3. {
  4.         for(int i=2;i*i<=x;i++)
  5.                 if(x%i==0)
  6.                         return 0;
  7.         return 1;
  8. }
  9. int main()
  10. {
  11.         int n,flag=0,sign=0;
  12.         scanf("%d",&n);
  13.         printf("%d=",n);
  14.         while(n>1)
  15.                 for(int i=2;i<=n;i++)
  16.                         if(judge)
  17.                                 while(n%i==0)
  18.                                 {
  19.                                         printf("%d",i);
  20.                                         n/=i;
  21.                                         if(n!=1)
  22.                                                 printf("*");
  23.                                 }
  24.         return 0;
  25. }
复制代码
作者: universehyf    时间: 2018-7-23 19:04
质因数分解
在火车上做的，花了一个多小时，不好，第一次是因为ss和ss表都用的I，循环n多次，第二次是因为ssb用的j，不稳定。第三次才合格。
  1. #include<iostream>
  2. #include<cmath>
  3. using namespace std;
  4. int bg[10010],c[10010];
  5. long long n,nn;
  6. int i,j=1,bj;
  7. bool pd;
  8. bool ss(int y)
  9. {
  10.     int sq=sqrt(y);
  11.     for(i=2;i<=sq;i++)
  12.         if(y%i==0) return false;
  13.     return true;
  14. }
  15. void ssb(int x)
  16. {
  17.     for(i=3;i<=n;i++)
  18.         if(ss(i)) bg[j++]=i;
  19. }
  20. int main()
  21. {
  22.     bg[0]=2;cin>>n;nn=n;ssb(n);bj=j-1;
  23.     cout<<j;
  24.     ///for(i=0;i<j;i++) cout<<bg[i];
  25.     for(i=0;i<j;i++)
  26.     {
  27.         while(n%bg[i]==0){c[i]++;n=n/bg[i];}
  28.         if(n==1) {bj=i;break;}
  29.     }
  30.     pd=false;
  31.     cout<<nn<<'=';
  32.     for(i=0;i<bj;i++)
  33.         for(j=0;j<c[i];j++)
  34.         {
  35.             if(pd) cout<<'*'<<bg[i];
  36.             else {cout<<bg[i];pd=true;}
  37.         }
  38.     if(!pd) cout<<'1';
  39.     return 0;
  40. }
复制代码
作者: 七夜劫年    时间: 2018-7-23 19:25
本帖最后由 七夜劫年 于 2018-7-23 19:36 编辑

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
int i=2;
int main()
{
        cin>>n;
        cout<<n<<"=";
        while( n != 1 )
        {
                if( n%i == 0 )
                {
                        cout<<i;
                        n/=i;
                        if( n != 1 )
                        {
                                cout<<"*";
                        }
                }
                else if( n%i != 0 )
                {
                        i++;
                }
        }
        return 0;
}
作者: 黄煦喆    时间: 2018-7-23 19:54
  1. #include<iostream>
  2. using namespace std;
  3. int n,x=2,a[100],t;
  4. int main()
  5. {
  6.     cin>>n;cout<<n<<'=';
  7.     while(n>1)
  8.     {
  9.         while(n%x==0)a[++t]=x,n/=x;
  10.         x++;
  11.     }
  12.     for(int i=1;i<t;i++)cout<<a[i]<<'*';
  13.     cout<<a[t];
  14.     return 0;
  15. }
复制代码
作者: zhwang    时间: 2018-7-23 19:56
#include<cstdio>
int n;
int biao;
int main()
{
        scanf("%d",&n);
        if(n==1)
        {
                printf("1=1*1");
                return 0;
        }
        printf("%d=",n);
        for(int i=2;i<=n;i++)
        {
                biao=1;
                for(int j=2;j<i;j++)
                {
                        if(i%j==0)
                        {
                                biao=0;
                                break;
                        }
                }
                if(biao==0)
                {
                        continue;
                }
                while(n%i==0&&n!=i)
                {
                        printf("%d*",i);
                        n/=i;
                }
                if(n==i)
                {
                        printf("%d",i);
                        {
                                break;
                        }
                }
        }
        return 0;
}
作者: 张笑宇    时间: 2018-7-23 20:40
  1. #include<iostream>
  2. #include<cmath>
  3. using namespace std;
  4. int n,i;
  5. int zs(int x)
  6. {
  7.     for (int k=2;k<=sqrt(x);k++)
  8.         if (x%k==0) return 0;
  9.     return 1;
  10. }
  11. int main()
  12. {
  13.     cin>>n;
  14.     cout<<n<<"=";
  15.     int i=2;
  16.     for (i=2;i<=sqrt(n);i++)
  17.     {
  18.         if (zs(i))
  19.         {
  20.             while (n%i==0)
  21.             {
  22.                 n=n/i;
  23.                 if (n==1)
  24.                 {
  25.                     cout<<i;
  26.                     return 0;
  27.                 }
  28.                 else cout<<i<<"*";

  30.             }
  31.         }
  32.     }
  33.     return 0;
  34. }
复制代码
作者: admin    时间: 2018-7-23 21:01
你们再好好想想，怎么都那么复杂呢？11点我来上我的程序。
作者: 白至白    时间: 2018-7-24 09:03
手机端好像就只能这样贴代码了
作者: 白至白    时间: 2018-7-24 09:04
#include<iostream>using namespace std;#define MAX_NUM 1000000char isPrime[MAX_NUM+10];//没给数据范围，先开个一百万吧 int main(){        for(int i=2;i<=MAX_NUM;++i)        isPrime[i]=1;        for(int i=2;i<=MAX_NUM;++i){                if(isPrime[i])                for(int j=2*i;j<=MAX_NUM;j+=i)                isPrime[j]=0;        }        int n;        cin>>n;        for(int i=2;i<=MAX_NUM&&n>1;)        if(isPrime[i]){                if(n%i==0){                        n/=i;cout<<i;                        if(n!=1)cout<<'*';                }                else ++i;        }        else ++i;         return 0;}
作者: 白至白    时间: 2018-7-24 09:09
#include<iostream>
using namespace std;
#define MAX_NUM 1000000
char isPrime[MAX_NUM+10];//没给数据范围，先开个一百万吧
int main(){       
for(int i=2;i<=MAX_NUM;++i)
        isPrime[i]=1;
        for(int i=2;i<=MAX_NUM;++i){       
        if(isPrime[i])
                for(int j=2*i;j<=MAX_NUM;j+=i)                isPrime[j]=0;        }       
int n;       
cin>>n;       
for(int i=2;i<=MAX_NUM&&n>1;)
        if(isPrime[i])  
                if(n%i==0)
                        n/=i;cout<<i;
                        if(n!=1)cout<<'*';       
}       
        else ++i;
        }
        else ++i;
        return 0;
}
作者: 黄诗绮    时间: 2018-7-24 20:22
  1. #include <iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.         int n,i=2;
  6.         cin>>n;
  7.         cout<<n<<'=';
  8.         do{
  9.                 while(n%i==0)
  10.                 {
  11.                         cout<<i;
  12.                         n/=i;
  13.                         if(n!=1) cout<<'*';
  14.                 }
  15.                 i++;
  16.         }
  17.         while(n!=1);
  18.         return 0;
  19. }
复制代码
作者: admin    时间: 2018-7-24 21:33
黄同学这个做法好！
作者: 倚窗倾听风吹雨    时间: 2018-7-25 07:44
  1. #include<iostream>
  2. #include<cmath>
  3. using namespace std;
  4. int n,m;
  5. int main()
  6. {
  7.         cin>>n;
  8.         cout<<n<<"=";
  9.         int i=2;
  10.         while(n>1)
  11.         {
  12.                 while(n%i==0)
  13.                 {
  14.                         n=n/i;
  15.                         cout<<i;
  16.                         if(n!=1)cout<<"*";
  17.                 }
  18.                 i++;
  19.         }
  20.         return 0;
  21. }
复制代码






欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2