C++(g++ 7.5.0) 解法, 执行用时: 13ms, 内存消耗: 468K, 提交时间: 2022-08-15 18:24:33

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
ll mul(ll a,ll b,ll mod)
{
	ll ans=0 ;
	while(b)
	{
		if(b&1) ans=(ans+a)%mod ;
		a=(a+a)%mod ; b>>=1 ;
	}
	return ans ;
}
ll qsm(ll a,ll b,ll mod)
{
	ll ans=1 ;
	while(b)
	{
		if(b&1) ans=mul(ans,a,mod) ;
		a=mul(a,a,mod) ; b>>=1 ;
	}
	return ans ;
}
bool M_check(ll a,ll n)
{
	if(n==2) return 1 ;
	if(n==1 || !(n&1)) return 0 ;
	ll d=n-1 ;
	while(!(d&1)) d>>=1 ;
	ll t=qsm(a,d,n) ;
	while(d!=n-1&&t!=1&&t!=n-1)
	{
		t=mul(t,t,n) ;
		d<<=1 ;
	}
	return t==n-1||d&1 ;
}
bool M_prime(ll n)
{
	if(n<=1) return 0 ;
	vector<ll> t={2,325,9375,28178,450775,9780504,1795265022} ; //检测用的数
	for(ll k:t)
	{
		//if(k==n) return 1 ; 如果用了奇质数加上这个判断
		if(n%k==0||!M_check(k,n)) return 0 ;
	}
	return 1 ;
}
mt19937 mt(time(0)) ;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a ; }
ll pollard_rho(ll n,ll c)
{
	ll x=uniform_int_distribution<ll>(1,n-1)(mt),y=x ;
	auto f=[&](ll v) { ll t=mul(v,v,n)+c ; return t<n?t:t-n ; };
	while(1)
	{
		x=f(x) ; y=f(f(y)) ;
		if(x==y) return n ;
		ll d=gcd(abs(x-y),n) ;
		if(d!=1) return d ;
	}
}
ll fac[100],fcnt ;
void get_fac(ll n,ll cc=19260817)
{
	if(n==4) { fac[fcnt++]=2 ; fac[fcnt++]=2 ; return ; }
	if(M_prime(n)) { fac[fcnt++]=n ; return ; }
	ll p=n ;
	while(p==n) p=pollard_rho(n,--cc) ;
	get_fac(p) ; get_fac(n/p) ;
}
void go_fac(ll n) { fcnt=0 ; if(n>1) get_fac(n) ; }
int main()
{
	int k ;
	cin>>k ;
	for(int i=2;i<=k;++i)
		if(M_prime(i))
		{
			unsigned ll t=((unsigned ll)1<<i)-1 ;
			if(M_prime(t)) continue ;
            go_fac(t) ;
			sort(fac,fac+fcnt) ;
			printf("%lld ",fac[0]) ;
			for(int j=1;j<fcnt;++j)
				printf("* %lld ",fac[j]) ;
			printf("= %lld = ( 2 ^ %d ) - 1\n",t,i) ;

		}
	return 0 ;
}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 428K, 提交时间: 2022-10-28 10:35:13

#include<bits/stdc++.h>
using namespace std;
const int N=50;
string a[500]={"23 * 89 = 2047 = ( 2 ^ 11 ) - 1","47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1","233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1","223 * 616318177 = 137438953471 = ( 2 ^ 37 ) - 1","13367 * 164511353 = 2199023255551 = ( 2 ^ 41 ) - 1","431 * 9719 * 2099863 = 8796093022207 = ( 2 ^ 43 ) - 1","2351 * 4513 * 13264529 = 140737488355327 = ( 2 ^ 47 ) - 1","6361 * 69431 * 20394401 = 9007199254740991 = ( 2 ^ 53 ) - 1","179951 * 3203431780337 = 576460752303423487 = ( 2 ^ 59 ) - 1"};
int aa[N]={11,23,29,37,41,43,47,53,59};
int main(){
    int k;
    cin>>k;
    for(int i=0;i<=10;i++){
        if(aa[i]<=k){
            cout<<a[i]<<"\n";
        }
    }
}