| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 760 人关注过本帖
标题:一个数分解成素数的乘积,放下代码,有兴趣的可以拿去耍耍
只看楼主 加入收藏
朱三哥
Rank: 5Rank: 5
等 级:职业侠客
威 望:1
帖 子:311
专家分:359
注 册:2012-12-11
结帖率:62.07%
收藏
 问题点数:0 回复次数:3 
一个数分解成素数的乘积,放下代码,有兴趣的可以拿去耍耍
程序代码:
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXPRIMENUM 100
static int primeroom[100];
int a[MAXPRIMENUM];
//生成素数函数 只有100个
void primenum_product()
{
     int i,j=2,k=0,n=0;
     while(n<MAXPRIMENUM){
         for(i=1;i<=j;i++){
             if(j%i==0)
             k++;
         }
         if(k==2){
            a[n]=j;
            n++;
           
         }
         j++;
         k=0;
     }
    
}
//用二分算法确定,给出的数值的平方根在上面生成素数的数组里的 位置确定
int sqrtnum_find(int sqrtnum,int n1,int n2 )
{
    int i=n2,n=(n1+n2)/2,j=n1;
    if(j-i>5){
       
        if(sqrtnum<a[n])
            sqrtnum_find(sqrtnum,n,i);
        else if(sqrtnum==a[n]){
             return(n);
             exit(0);
        }
        else
            sqrtnum_find(sqrtnum,j,n);
    }
     else{
       for(i;i<=j;i++)
       if(sqrtnum<=a[i]){
          return(j);
          exit(0);
        }
       }
      
}

//将一个数分解成几个素数的乘积的算法,嘿嘿,不懂算法怎么走起的,请看离散数学第二章
void primenum_reduce(int interger,int n)
{
    int sqrtnum,primenum=1,i=1,j,interger1;
    for(j=0;j<MAXPRIMENUM;j++){
        if(interger==a[j]) {
            primeroom[n]=a[j];
            i=0;
        }
    }
    if(i!=0){
    sqrtnum=(int)sqrt(interger);
    if(sqrtnum>=1){
        i=sqrtnum_find(sqrtnum,MAXPRIMENUM-1,0);
        for(j=0;j<i;j++){
            if(interger%a[j]==0){
                primenum*=a[j];
                primeroom[n]=a[j];
                n++;
                interger1=interger/a[j];
                break;
            }
        }
     primenum_reduce(interger1,n);
    }
    }
}

void main()
{
    int interger,i;
    primenum_product();
    printf("请输入一个正整数:\n");
    scanf("%d",&interger);
    primenum_reduce(interger,0);
    for(i=0;i<100;i++){
        if(primeroom[i]!=0)
             printf("素数因子:%d\n",primeroom[i]);
        else
            break;
    }
}

   



[ 本帖最后由 朱三哥 于 2013-1-21 12:04 编辑 ]
搜索更多相关主题的帖子: color 
2013-01-21 00:47
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
膜拜


[fly]存在即是合理[/fly]
2013-01-21 02:20
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:0 
就从小往大找素因子,如果发现正在排查的素数已经比平方根大就停。这样是不是可以省去二分搜索呢?
2013-01-22 08:32
yaobao
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:蒙面侠
威 望:4
帖 子:1854
专家分:4121
注 册:2012-10-25
收藏
得分:0 
好长

认认真真的学习,踏踏实实的走路:戒骄戒躁!!!
2013-01-22 12:00
快速回复:一个数分解成素数的乘积,放下代码,有兴趣的可以拿去耍耍
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.033284 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved