李敏  
日历
<2024年5月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678
统计
  • 随笔 - 1
  • 文章 - 40
  • 评论 - 4
  • 引用 - 0

导航

常用链接

留言簿(1)

文章分类

文章档案

相册

收藏夹

它山之石

聚贤庄

搜索

  •  

最新评论

 
找出1~100之间的有12个公约数的整数。

例:6
1、2、3、6    
6的公约数为4。

分析:
1 首先此整数一定为偶数,因为100以内的任意一个奇数的公约数不可能达到12个这么多。

2 经过几个偶数的公约数的分析,可以得出倒数第二个公约数是该数的1/2。也就是说(整数/2>=11,即整数>=22)。

3 因为有12个公约数:第一,该数一定能被6整除(同样根据几个偶数的公约数分析得到,整数一定可以整除【公约数/2】);第二,既然达到了12个公约数,所以肯定超过了10,既然可以被6整除,那余数自然>=10。

4 因为有12个公约数,所以1~12范围内就最少包括了12/2个公约数(就是一半的公约数),然而真正能够被整除的实际的公约数只有10个(除去1和它本身),则10以内的公约数必须达到5个。

5 如果10以内的公约数达到了5个,则从11~(整数/2)继续查找,当找到第10个公约数时停止,然后继续判定下一个整数。


1~2  整数取值范围。

3  整数的过滤条件。

4~5  约数的过滤条件。

    int num=0;
    
     for(int i=4;i<17;i++){
        int k=i*6;
       
         for(int j=10;j>=2;j--){
            if(k%j==0){
               num++;
              
              if(j==5&&num<2){
                num=-1;
                break;
              }
            }
         }
   
        
         if(num>=5){
           for(int j=11;j<=k/2&&num!=10;j++){
              if(k%j==0)
              num++;
           }
         }
      
        if(num==10){
          System.out.println(k);
        }
           num=0;         
     }
posted on 2009-08-31 15:00 李敏 阅读(300) 评论(0)  编辑  收藏 所属分类: 算法

只有注册用户登录后才能发表评论。


网站导航:
 
 
Copyright © 李敏 Powered by: 博客园 模板提供:沪江博客