题意分析

i从1到k，如果是素数，看2的i次方减1是否为合数，如果是，看是否能拆成几个素数相乘。

解题思路

用大整数因式分解Pollard_rho算法和大整数素数判断miller_rabin。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
#define ll long long
bool prim[65];
int p[65];
int cnt;
ll yz[111111];
void init()
{
    memset(prim,true,sizeof(prim));
    cnt=0;
    for(int i=2;i<64;i++)
    {
        if(prim[i])
        {
            p[cnt++]=i;
            for(int j=i*2;j<64;j+=i)
                prim[j]=false;
        }
    }
}
ll mul(ll x,ll y,ll mod)
{
    ll ans=0;
    while(y)
    {
        if(y&1)ans=(ans+x)%mod;
        x=(x+x)%mod;
        y>>=1;
    }
    return ans;
}
ll poww(ll x,ll y,ll mod)
{
    ll ans=1;
    while(y)
    {
        if(y&1)ans=mul(ans,x,mod);
        x=mul(x,x,mod);
        y>>=1;
    }
    return ans;
}
bool miller_rabin(ll n)
{
    ll t,u,a,x,y;
    if(n==2)return true;
    if(n==1||!(n&1))return false;
    for(t=0,u=n-1;!(u&1);t++,u>>=1);
    for(int i=0;i<10;i++)
    {
        ll a=rand()%(n-1)+1;
        x=poww(a,u,n);
        for(int j=0;j<t;j++)
        {
            y=mul(x,x,n);
            if(y==1&&x!=1&&x!=n-1)
                return false;
            x=y;
        }
        if(x!=1)
            return false;
    }
    return true;
}
ll gcd(ll a,ll b)
{
   if(a<0)
        return gcd(-a,b);
        if(a==0)
            return 1;
    while(b)
    {
        long long int t=a%b;
        a=b;
        b=t;
    }
    return a;
}
int num;
ll Pollard_rho(ll n,ll c)
{
    int i=1,k=2;
    ll x=rand()%(n-1)+1;
    ll y=x;
    while(1)
    {
        i++;
        x=(mul(x,x,n)+c)%n;
        ll p=gcd(y-x,n);
        if(p!=1&&p!=n)
            return p;
        if(y==x)
            return n;
        if(i==k)
        {
            y=x;
            k+=k;
        }
    }
}
void findx(ll n)
{
    if(n==1)return;
    if(miller_rabin(n))
    {
        yz[num++]=n;
        //cout<<n<<endl;
        return ;
    }
    ll p=n;
    while(p>=n)
        p=Pollard_rho(p,rand()%(n-1)+1);
    findx(p);
    findx(n/p);
}
int main()
{
   init();
   int k;
   //ll z=2047;
  // findx(z);
   while(~scanf("%d",&k))
   {
        for(int i=0;i<cnt;i++)
        {
 
            if(p[i]<k)
            {
                ll kk=(1ll<<p[i])-1;
               // cout<<p[i]<<' '<<kk<<endl;
                if(!miller_rabin(kk))
                {
                    //cout<<kk<<' ';
                    num=0;
                    findx(kk);
                    sort(yz,yz+num);
                    int ss=0;
                    printf("%lld",yz[0]);
                    for(int j=1;j<num;j++)
                    {
 
                        printf(" * %lld",yz[j]);
                    }
                    printf(" = %lld = ( 2 ^ %d ) - 1\n",kk,p[i]);
                }
            }
        }
   }
   return 0;
}