精华内容
下载资源
问答
  • 最多约数问题

    千次阅读 2018-12-17 22:39:14
    算法分析与设计——实验一:算法复杂性分析问题:最多约数问题:正整数x的约数是能整除x的正整数。正整数x 的约数个数记为div(x)。例如,1,2,5,10 都是正整数10 的约数,且div(10)=4。设a 和b 是2 个正整数,a≤b...

    问题

    • 最多约数问题:正整数x的约数是能整除x的正整数。正整数x 的约数个数记为div(x)。例如,1,2,5,10 都是正整数10 的约数,且div(10)=4。设a 和b 是2 个正整数,a≤b,找出a和b之间约数个数最多的数x及其最多约数个数。

    方法

    • 枚举法:枚举区间(a, b)内的所有整数,统计他们的约数个数,找出约数最多的整数。
    • 质因子法:取出区间(a,b)内的所有整数,判断是否能被以此增长的素数整除,若能被整除则该素数进行指数增长判断是否能被整除直至素数的指数倍大于该整数,记录指数大小,若此时已得到该整数,则利用公式正整数x的质因子分解为:x=p1^N1 × p2^N2 ×……pi^Ni,则div(x)=(N1+1)(N2+1)……(Ni+1)求得约数个数,否则继续验证素数。

    代码

    • 枚举法
    #include <stdio.h>
    #include <stdlib.h> 
    int main()
    {      
      int i=1,j=0,k=1,a,b,max=0,m=0,count[100]={0};   	  
      scanf("%d %d",&a,&b);    
      for(;i<b-a;i++)//循环依次找出在(a,b)区间的整数   
      {  
         for(j=0,k=1;k<=a+i;k++)//从一开始遍历	
         {   
             if((a+i)%k==0)                
             j++;}//若k能整除此整数,则约数个数加一        
         count[i]=j;        
         if(j>=max) //找出最多约数个数        
         {  
            max=j;            
            m=i;} //将当前有最大约数个数的整数赋给m    
      }    
      for(i=0;i<b-a;i++)     
      {        
         if(count[i]==max)             
         printf("%d %d\n",a+i,max);    
      }
     }
    
    • 质因子法
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    int main()
    {    
       int i=1,m=1,s=1,a,b,t=0,j=0,k=0,max=0,c[100]={0};    
       scanf("%d %d",&a,&b);    
       for(;i<b-a;i++)//循环依次找出在(a,b)区间的整数    
       {        
           t=a+i;        
           for(j=2;j<=t;j++)//枚举不大于该整数的所有素数       
           {            
               if(t%j==0)//若t能被j整除            
               {                
                   for(k=2;pow(j,k)<=t;k++)                
                   {                    
                       if(t%(int)(pow(j,k))==0)//判断j的k次方是否能整除t                        
                       s=k;//将最大k值赋给s                
                   }                
                   m=m*(s+1);//利用公式求得当前约数个数               
                   if(t==pow(j,s))                    
                       break;//若j的s次方等于t,跳出循环,判断下一个整数               
                   else                    
                       t=t/pow(j,s);//若j的s次方不等于t,将t赋予新值                
                   s=1;            
               }       
           }        
           c[i]=m;//将得到的约数个数m赋给c[i]        
           m=1;//将m置1        
           if(c[i]>=max)            
                max=c[i];//得到最大约数个数    
       }    
       for(i=1;i<b-a;i++)   
       {       
          if(c[i]==max)             
          printf("%d %d\n",a+i,max);
       }
    }
    
    展开全文
  • 晚生才疏学浅,初来乍到,有很多问题,望与大家一起学习...2013年9月28* All Rights Reserved,西华师大计算机学院* 作 者:曾舜尧* 问题描述:从文件中读取两个数,计算两个数间隔内的约数最多的那个数(教材 Page ...

    晚生才疏学浅,初来乍到,有很多问题,望与大家一起学习进步!

    /***************************************************************************

    * 2013年9月28

    * All Rights Reserved,西华师大计算机学院

    * 作 者:曾舜尧

    * 问题描述:从文件中读取两个数,计算两个数间隔内的约数最多的那个数(教材 Page 9)

    * 算法分析:穷举法,对于给定的2个正整数,a<=b,计算a和b之间约数最多的数.

    * 数据输入:从文件读取2个正整数啊、和b.

    * 数据输出:若找到的a和b之间约数个数最多的数是result,则将div(约数个数)输出到文件

    * 备注:因不会文件操作,此程序采用键盘输入

    **************************************************************************/

    #include "stdio.h"

    int searchDivisor(int a)

    {

    int count=0;

    for(int i=1;i<=a;i++)

    {

    if(0==a%i)

    {

    count++;

    }

    }

    return count;

    }

    int main()

    {

    int a=0;//下界

    int b=0;//上界

    char tag='n';//继续标记

    int result=0;//目标数

    int div=0;//约数个数

    int temp=0;//临时存储

    do{

    printf("请输入两个合法数:");

    scanf("%d%d",&a,&b);

    if(a<0||b<0)

    {

    printf("输入错误!\n");

    return 0;

    }

    for(;a<=b;a++)

    {

    temp=searchDivisor(a);

    if(temp>div)

    {

    div=temp;

    result=a;

    }

    }

    printf("数%d有%d个约数!\n",result,div);

    //stdin.flush();

    printf("是否继续(y/n):");

    scanf("%c",&tag);

    }

    while('y'==tag||'Y'==tag);

    return 0;

    }

    /*注释*/

    小弟对文件操作很是畏惧,望大师赐教!

    展开全文
  • 质因数分解法-最多约数问题最多约数问题 最多约数问题 最多约数问题:正整数x的约数是能整除x的正整数。正整数x 的约数个数记为div(x)。例如,1,2,5,10 都是正整数10 的约数,且div(10)=4。设a 和b 是2 个正整数...

    质因数分解法-最多约数问题

    最多约数问题

    最多约数问题:正整数x的约数是能整除x的正整数。正整数x 的约数个数记为div(x)。例如,1,2,5,10 都是正整数10 的约数,且div(10)=4。设a 和b 是2 个正整数,a≤b,找出a和b之间约数个数最多的数x及其最多约数个数。

    // An highlighted block
    #include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        set <int> se;
        set<int>::iterator it;
        int sum[100001];
        int n,m,x,max=-1,count=1;
        cin>>n>>m;
        for(int nub=n;nub<=m;nub++){
            x=nub;
            memset(sum,0,sizeof(sum));
            se.clear();
            for(int i=2;i<x;i++){
            while(i!=x){
                if(x%i==0){
                    sum[i]++;
                    se.insert(i);
                    x=x/i;
                }
                else break;
                }
            }
            sum[x]++;
            se.insert(x);
            it =se.begin();
            count=1;
            while(it!=se.end()){
                count=count*(sum[*it]+1);
                it++;
            }
            if(count>max){
                max=count;
            }
        }
        cout<<max;
    }
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 233
精华内容 93
关键字:

最多约数问题