不是吧
只要正向得到
形式如2pq + 1 类型素数就可以了吧
对 2048 以内的素数分组 有 92 组的结果：
No. 1 : 2039 2029 1033
No. 2 : 2027 2017 1049
No. 3 : 2011 2003 1063
No. 4 : 1999 1997 1069
No. 5 : 1993 1987 1061
No. 6 : 1979 1973 1097
No. 7 : 1951 1949 1129
No. 8 : 1933 1931 1123
No. 9 : 1913 1907 1171
No. 10 : 1901 1889 1193
No. 11 : 1879 1877 1217
No. 12 : 1873 1871 1223
No. 13 : 1867 1861 1231
No. 14 : 1847 1831 1259
No. 15 : 1823 1811 1297
No. 16 : 1801 1789 1327
No. 17 : 1787 1783 1321
No. 18 : 1777 1759 1373
No. 19 : 1753 1747 1399
No. 20 : 1741 1733 1423
No. 21 : 1723 1721 1447
No. 22 : 1709 1699 1471
No. 23 : 1697 1693 1493
No. 24 : 1669 1667 1543
No. 25 : 1663 1657 1553
No. 26 : 1637 1627 1609
No. 27 : 1621 1619 1613
No. 28 : 1607 1601 1597
No. 29 : 1583 1579 1571
No. 30 : 1567 1559 1549
No. 31 : 1531 1523 1511
No. 32 : 1499 1489 1487
No. 33 : 1483 1481 1459
No. 34 : 1453 1451 1439
No. 35 : 1433 1429 1427
No. 36 : 1409 1381 1367
No. 37 : 1361 1319 1307
No. 38 : 1303 1301 1291
No. 39 : 1289 1283 1279 2
No. 40 : 1277 1249 1237
No. 41 : 1229 1213 1201
No. 42 : 1187 1181 1163
No. 43 : 1153 1151 1117
No. 44 : 1109 1103 1093 3
No. 45 : 1091 1087 1051
No. 46 : 1039 1031 1021
No. 47 : 1019 1013 1009
No. 48 : 997 991 983
No. 49 : 977 971 967
No. 50 : 953 947 941 5
No. 51 : 937 929 919
No. 52 : 911 907 887
No. 53 : 883 881 877
No. 54 : 863 859 857
No. 55 : 853 839 829 7
No. 56 : 827 823 821
No. 57 : 811 809 797
No. 58 : 787 773 769
No. 59 : 761 757 751
No. 60 : 743 739 733
No. 61 : 727 719 709 11
No. 62 : 701 691 683
No. 63 : 677 673 661 13
No. 64 : 659 653 647
No. 65 : 643 641 631
No. 66 : 619 617 613 17
No. 67 : 607 601 599 19
No. 68 : 593 587 577
No. 69 : 571 569 563 23
No. 70 : 557 547 541
No. 71 : 523 521 509 29
No. 72 : 503 499 491 31
No. 73 : 487 479 467 37
No. 74 : 463 461 457 43
No. 75 : 449 443 439 47
No. 76 : 433 431 421 53
No. 77 : 419 409 401 61
No. 78 : 397 389 383 71
No. 79 : 379 373 367 79
No. 80 : 359 353 349 97
No. 81 : 347 337 331 109
No. 82 : 317 313 311 139
No. 83 : 307 293 283 167
No. 84 : 281 277 271 199
No. 85 : 269 263 257 233
No. 86 : 251 241 239 229
No. 87 : 227 223 211 197
No. 88 : 193 191 181 179
No. 89 : 173 163 157 151
No. 90 : 149 137 131 127
No. 91 : 113 107 103 83 41
No. 92 : 101 89 73 67 59
楼上说说，你是如何做到的？
这个悬赏至今刚好满一个月了，
之前一直没有更好的突破，
所以，打算继续悬赏一个月，
对于有突破的算法或结论，
除了可以得到悬赏的100枚金币，
还可获得本人私下转让的金币（数目不菲的）。
#include < iostream.h >
#include < math.h >
#include "D:/HugeCalc/HugeCalc.h"// 公共接口
#include "D:/HugeCalc/HugeInt.h" // 10进制系统
#include "D:/HugeCalc/HugeIntX.h"// 16进制系统
#pragma message( "automatic link to D:/HugeCalc/HugeCalc.lib" )
#pragma comment( lib, "D:/HugeCalc/HugeCalc.lib" )
const unsigned __int16 Pri1024 = 172; // 1024 以内的素数个数
const unsigned __int16 Pri2048 = 309; // 2048 以内的素数个数
const __int64 BOUND32 = (1ul << 32) - 1;
const __int64 BOUND14 = (1ul << 14) - 1;
const __int64 BOUND10 = (1ul << 10) - 1;
typedef CHugeIntX integer;
unsigned __int16 arr[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039 };
//const unsigned __int32 ProblemSize = 1023;
//unsigned __int16 arr;
__int32 MinimumGroup(const unsigned __int16* const arr, const unsigned __int16 _SIZE, const __int64 _BOUND);
int main(/*int argc, char* argv[]*/ void)
{
__int32 result;
//for ( __int16 i=0; i<ProblemSize; i++) arr[ i ] = i + 2;
cout << "Call " << HugeCalc::GetVer() << endl;
HugeCalc::EnableTimer();
HugeCalc::ResetTimer(0, TIMER_UNIT_ms);
//result = MinimumGroup(arr, ProblemSize, BOUND32);
//result = MinimumGroup(arr, 25, BOUND14); // 贪婪法=10，最优=9
//result = MinimumGroup(arr, 36, 22500ul); // 贪婪法=15，最优=14
//result = MinimumGroup(arr, 72, 8100ul); // 贪婪法=最优=49
//result = MinimumGroup(arr, Pri1024, BOUND10); // 贪婪法=最优=162
//result = MinimumGroup(arr, Pri1024, BOUND10*29); // 贪婪法=最优=133
result = MinimumGroup(arr, Pri1024, BOUND32);
//result = MinimumGroup(arr, Pri2048, BOUND32);
HugeCalc::EnableTimer( FALSE );
cout << endl << "Best result = " << result << endl;
cout << endl << HugeCalc::GetTimerStr() << endl;
system( "pause" );
return 0;
}
// 函数名： MinimumGroup
// 函数功能： 求出把一组正整数 arr ~ arr 划分成最少的组数的方法，使得每组里所有数之积均不大于 _BOUND
//
// 输入参数:
// arr： unsigned __int16，数组指针，要求 arr[] 是升序排列
// _SIZE：unsigned __int16，数组的大小
// _BOUND： __int64，分组的乘积最大值
//
// 输出参数： __int32，最小分组数
// 结果为0： _SIZE = 0
// 结果为 -1： _BOUND < arr
// 结果为 -2： arr 不是升序排列
//
// 版本 ： 1.2.5.9
// 修改时间： 2008-9-11 00:30
//
// 存在问题： 运算效率很低，限界条件不够精细
// 下一版本改进措施； 乘法变加法，把 arr[]、_BOUND 都取对数，然后扩大某个倍数，化成整数加减运算
__int32 MinimumGroup(const unsigned __int16* const arr, const unsigned __int16 _SIZE, const __int64 _BOUND)
{
__int32 i, j, k, icur, g, gMin, gMax, gCur, top, bottom, top0, bottom1, top1, Lpro, numOfBig, Lpromin;
__int32 *bUsed, *pbuf;
__int64 product, maxV, minGV, *pmaxV, *pminGV, *ppro;
top0 = _SIZE - 1;
if ( 0 == _SIZE ) return (0);
if ( _BOUND < arr ) return (-1);
for ( i=0; i<top0; ++i )
{
if ( arr > arr )
return (-2);
}
if ( 0 == arr || 1 == arr ) return (1);
for ( i=0 ;1 == arr ;++i ); // 1不参加运算
if ( i == top0 ) return (1);
bottom1 = i;
for (maxV=_BOUND/arr, i=top0 ; i>bottom1 && arr>maxV ; --i ); // 只能单独做一组的数
if ( i - bottom1 < 2 ) return (_SIZE - i);
top1 = i;
integer hollpro(arr), grpV(_BOUND), b(_BOUND);
for ( j=1, i=1+bottom1 ;i<=top1 ;++i )
{
hollpro *= arr;
if ( hollpro > grpV )
{
grpV *= b;
++j;
}
}
grpV = 0;
numOfBig = top0 - top1;
gMin = j + numOfBig;
if ( j == 1 ) return (gMin);
// 用贪婪法求分组数的一个上界 gMax，此方法来自 gxqcn
bUsed = new __int32 ;
for ( i=0; i<_SIZE; ++i ) bUsed = 0;
cout << endl;
for ( gMax=0, bottom=0, top=top0 ;bottom != top ; )
{
++gMax;
cout << "No. " << gMax << " : ";
//for ( product=1, maxV=_BOUND, i=top ; i >= bottom;--i )
for ( maxV=_BOUND, i=top ; i >= bottom;--i )
{
if ( !bUsed && arr <= maxV )
{
cout << " " << arr;
//maxV = _BOUND / ( product *= arr );
maxV /= arr;
bUsed = 1;
}
}
//cout << " " << product;
cout << endl;
while ( bottom != top && bUsed ) --top;
while ( bottom != top && bUsed ) ++bottom;
}
if ( !bUsed )
{
++gMax;
//cout << "No. " << gMax << " : " << arr << " " << arr << endl;
cout << "No. " << gMax << " : " << arr << endl;
}
if ( gMax == gMin )
{
delete [] bUsed;
return (gMax); // 上界 = 下界
}
// 尝试组数更小的方案
// 求第一组的数字的个数
for ( Lpromin=0, maxV=_BOUND, i=top1 ; i >= bottom1;--i )
{
if ( arr <= maxV )
{
maxV /= arr;
++Lpromin;
}
}
k = gMax - numOfBig;
for ( maxV=_BOUND, i=bottom1; arr<=maxV; ++i ) maxV /= arr ;
Lpro = i - bottom1 + 1; // 最长乘式的因子数+1
j = Lpro * gMax;
pbuf = new __int32 ; // 所有分组因子下标表格
pmaxV = new __int64 ; // 同组的下一个乘积因子允许的最大值
ppro = new __int64 ; // 本组前几个因子的乘积
pminGV = new __int64 ;// 每一组乘积允许的最小值
integer *pGV, *pB, q, r, c;
pGV = new integer ; // 本组之后未分配的数的乘积
pB = new integer ; // 界限参数（_BOUND的乘幂）
for ( i=0; i<j; ++i ) pbuf = 0;
for ( i=0; i<j; ++i ) pmaxV = 0;
for ( i=0; i<j; ++i ) ppro = 0;
for ( top=top0, i=1; i<=numOfBig ; ++i, --top )
{
pbuf = 1;
pbuf = top;
ppro = 1;
ppro = arr;
bUsed = 1;
}
icur = Lpro-2+bottom1;
if ( Lpromin <= 2 )
{
for ( i=icur; i<top1; ++i ) pmaxV = _BOUND - ( _BOUND % arr );
}
else
{
for ( i=icur; i<top1; ++i )
{
maxV = _BOUND / arr;
g = __int32(maxV % arr);
for ( j=bottom1+1; g>0 && j<i; ++j)
{
gCur = __int32(maxV % arr);
if ( g > gCur )
g = gCur;
}
pmaxV = ( maxV - g ) * arr;
}
}
// 选择排序
for ( i=icur; i<icur+k-1; ++i )
{
for ( g=i, maxV=pmaxV, j=i+1; j<top1; ++j )
{
if ( maxV < pmaxV )
{
maxV = pmaxV;
g = j;
}
}
if ( g != i )
{
pmaxV = pmaxV;
pmaxV= maxV;
}
}
for ( pB=1, pB=pmaxV, j=icur, i=2; i<k; ++i )
{
++j;
pB = pB * ( q = pmaxV );
}
//for ( pB=1, pB=b, i=2; i<k; ++i ) pB = pB * b;
b = 0;
for ( i=numOfBig+1; i<gMax; ++i ) pmaxV= _BOUND;
pGV = hollpro;
for ( gCur=gMax-1 ;gCur >= gMin ;--gCur ) // 组数循环
{
for ( top=top1, i=bottom=bottom1; i<=top; ++i ) bUsed = 0;
for ( g=numOfBig+1 ; g<gCur ;) // g 循环
{
q.Div( pGV, pB, &r );
if ( !(!r) ) ++q;
pminGV = minGV = q;
k = 1;
pbuf = top;
ppro = product = arr;
pmaxV = maxV = _BOUND / product;
bUsed = 1;
icur = --top;
// 生成第 g 组乘积
do {
for ( i=icur; i>=bottom; --i )
{
if ( !bUsed && arr <= maxV )
{
++k;
pbuf = i;
ppro = product *= arr;
pmaxV = maxV /= arr ;
bUsed = 1;
}
}
if ( product >= minGV ) // 进入下一组
{
pbuf = k;
pGV = pGV / (c = product);
while ( bottom != top && bUsed ) --top;
while ( bottom != top && bUsed ) ++bottom;
++g;
break;
}
// 生成下一个乘积
do {
j = bottom;
do {
i = pbuf;
bUsed = 0;
--k;
if ( i > top )
{
top = i;
}
else if ( i < bottom )
{
bottom = i;
}
} while ( k >= 1 && i < j );
if ( k >= 1 )
{
icur = --i;
maxV = pmaxV;
product = ppro;
break;
}
--g; // 退回到上一组
if ( numOfBig == g ) // 退到底了
{
delete [] pB;
delete [] pGV;
delete [] pminGV;
delete [] ppro;
delete [] pmaxV;
delete [] pbuf;
delete [] bUsed;
return (gCur+1);
}
k = pbuf;
minGV = pminGV;
} while ( 1 ); // end of 生成下一个乘积
} while ( 1 ); // end of 生成第 g 组乘积
} // end of g 循环
for ( j=0, i=top; i>=bottom; --i) // 最后一组
{
if ( !bUsed )
{
++j;
pbuf = i;
}
}
pbuf = j;
// 输出
cout << endl << "groups = " << gCur << endl;
for ( i=1 ;i <= gCur ;++i )
{
cout << "No. " << i << " : ";
for ( k=pbuf, j=1 ;j <= k ;++j )
cout << " " << arr[ pbuf ];
cout << endl;
}
cout << endl;
} // end of 组数循环
delete [] pB;
delete [] pGV;
delete [] pminGV;
delete [] ppro;
delete [] pmaxV;
delete [] pbuf;
delete [] bUsed;
return (gMin);
}
这么说来，我给出的程序效率是很高的，结果也是相当不错的。
谢谢你的代码，有空时我琢磨一下。
前面第26#说了，该问题更注重输出结果，因为是拿它作应用的；
即便运行时间长点也不碍事，反正只要运行一次。
当然，若有更优化的通用算法，则是上上品了。
:)
为什么不用对数？
仅仅是因为是浮点运算？
假设某组数字的对数和为s
s <= 32
32 - s <= 1/16
是否算和优化的一组？
这跟一维下料是等价问题。只求满足根数最少的组合方式之一?(可能有多种)