首页 > 其他 > 详细

质因数分解

时间:2017-11-15 11:27:19      阅读:36      评论:0      收藏:0      [点我收藏+]

标签:cout   因数分解   ()   方法   flag   nbsp   space   下一个   质因数分解   

首先,你得先知道任意一个合数可以拆分成若干个素数之积

例如:24=2*2*2*3

然后就简单了,我是先取得一定量的素数(用之前写的素数筛),而后看能否整除,能就继续,不能就除下一个素数。

 

贴代码:

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int main()
{
    //先筛素数
    int num=0;
    int prime[10000];                   //用于存放素数
    int flag[10005];                    //用于判断i是否为素数
    memset(flag,0,sizeof(flag));
    for(int i=2;i<=10000;i++){
        if(flag[i]==0){
            prime[num++]=i;
            for(int j = i+i; j<=10000; j+=i)
                flag[j]=1;
        }
    }
    int n;                          //合数
    cin>>n;
    cout<<n<<"=";
    int p=0;
    bool q=0;                       //用于处理第一个输出的数
    while(n!=1){
        if(n%prime[p]==0){
            if(q==0){
                cout<<prime[p];
                q++;
            }
            else{
                cout<<"*"<<prime[p];
            }
            n=n/prime[p];
        }
        else
            p++;
    }
    return 0;
}

貌似有更优化的方法,尚未学习,等以后学了再更

 

质因数分解

标签:cout   因数分解   ()   方法   flag   nbsp   space   下一个   质因数分解   

原文:http://www.cnblogs.com/xinzhiyan/p/7837987.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号