注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1333  

2012-07-02 14:18:34|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1333

素数筛选法+分拆素数+求各个位之和

因为最大到100000000,所以素数筛选到10000即可
首先用素数筛选法列出一个素数表,只筛选到10000
然后对每个数进行分拆成几个素数,并累加该数的各个位之和,如果该数等于总和,那就是Smith数

还有,,这个数本身不应该是素数

#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<iostream>
using namespace std;
#define N 10010
bool f[N];
int prime[N];
void fun()
{
//用素数筛选法建立素数表
int i,j,pNum;
pNum=0;
  memset(f,true,sizeof(f));
  for(i=1;i<=N/2;i++)
  {
  if(!f[i])
  prime[pNum++]=i;
  for(j=2;j*i<=N;j++)
f[j*i]=false;
  }
}


bool Judge(int n)
{
//判断是否为素数
if(n==1)
return false;
int i;
    for(i=0;prime[i]*prime[i]<=n;i++)
    if(!(n%prime[i]))
    return false;
    return true;
}

int sum(int a)
{
//求数的各个位之和
    int s;
    s=0;
    while(a)
    {
        s+=a%10;
        a/=10;
    }
    return s;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("testin.txt","r",stdin);
#endif
    int n,i,s,a,p;
    fun();
    while(scanf("%d",&n)!=EOF && n)
    {
        while(n++)
        {
            if(Judge(n)) //如果该数是素数就continue
            continue;
        s=0;p=n;
        for(i=2;i*i<=p;i++)
        {
        if(p%i==0)
        {
        p/=i;
        a=sum(i);
        s+=a;
        while(p%i==0)
        {
        p/=i;
        s+=a;
        }
        }
        }
        if(p>1)
        s+=sum(p);
            if(sum(n)==s)
            {
                printf("%d\n",n);
                break;
            }
        }
    }
    return 0;
}
  评论这张
 
阅读(162)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018