约数和定理：

若n的标准分解式为 p1^k1 * p2^k2 ……

那么n的约数和= π （Σ pi^xi ） xi∈[0,ki]

原本枚举小于S的质数，通过先判断S-1是不是质数 就可以 枚举根号S内的质数

 

#include
     
      #include
      
       using namespace std;#define N 1000000int prime[N+1],cnt;bool vis[N+1];int ans[N],tot;void pre(){    vis[1]=true;    for(int i=2;i<=N;++i)    {        if(!vis[i]) prime[++cnt]=i;        for(int j=1;j<=cnt;++j)        {            if(i*prime[j]>N) break;            vis[i*prime[j]]=true;            if(!(i%prime[j])) break;        }    }}bool isprime(int x){    if(x<=N) return !vis[x];    for(int i=1;prime[i]*prime[i]<=x;++i)        if(!(x%prime[i])) return false;    return true;}void dfs(int last,int num,int rest){    if(rest==1) { ans[++tot]=num; return; }    if(rest-1>prime[last] && isprime(rest-1)) ans[++tot]=num*(rest-1);    for(int i=last+1;prime[i]*prime[i]<=rest;++i)        for(int sum=prime[i]+1,nnum=prime[i];sum<=rest;nnum*=prime[i],sum+=nnum)            if(!(rest%sum)) dfs(i,num*nnum,rest/sum);}int main(){    pre();    int n;    while(scanf("%d",&n)!=EOF)    {        tot=0;        dfs(0,1,n);        sort(ans+1,ans+tot+1);        printf("%d\n",tot);        for(int i=1;i<=tot;++i) printf("%d ",ans[i]);        if(tot) printf("\n");    }}