寻找最小素数P，满足如下条件

无心人

对所有小于100的素数$p_i$
使得$P -= (p_i - 1)   mod p_i$
即$P -= 1 (mod 2), \quad p-=2 (mod 3), \quad p-= 4 (mod 5) ...  p-= 96 (mod 97)$
要求程序行越少越好，运行时间不得超过1分钟
只能使用标准库

哈哈

[ 本帖最后由 无心人 于 2008-6-26 16:35 编辑 ]

mathe

$p_1$是什么？2？

mathe

这个不就是
$P=\prod_{p_i<100} p_i -1$

无心人

素数阿

老大

mathe

哦，那你得加条件P也是素数,也得先将我上面那个乘积计算出来，然后找最小的$lambda$,使得$lambda \prod_{p_i<100}p_i-1$是素数

mathe

不过只允许使用标准库做起来比较麻烦

无心人

呵呵，公式都出来了阿

[ 本帖最后由 无心人 于 2008-6-26 17:18 编辑 ]

gxqcn

Call HugeCalc V8.0.0.0
0.000878 s      λ = 4
P=9222271855782073699012408589327024279
请按任意键继续. . .

代码如下：

1. // HugeCalcDemo.cpp : Defines the entry point for the console application.
   
2. //
   
3. 
   
4. //        Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
   
5. //                Win32 Debug:        Debug Multithreaded DLL
   
6. //                Win32 Release:        Multithreaded DLL
   
7. 
   
8. #include <stdio.h>
   
9. 
   
10. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"        // 公共接口
    
11. #include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h"        // 10进制系统
    
12. #include "../../../HugeCalc_API/CppAPI/Include/HugeIntX.h"        // 16进制系统
    
13. 
    
14. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
    
15. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
    
16. 
    
17. #if 1
    
18.         #define _Test_HI
    
19.         #define integer CHugeInt
    
20. #else
    
21.         #define _Test_HX
    
22.         #define integer CHugeIntX
    
23. #endif
    
24. 
    
25. int main(int argc, char* argv[])
    
26. {
    
27. //        printf("Hello World!\n");
    
28. 
    
29.         printf( "Call %s\r\n", HugeCalc::GetVer());
    
30. 
    
31.         if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
    
32.         {
    
33.                 printf( "\r\n警告：您未通过 HugeCalc.dll 的许可认证！\r\n" \
    
34.                         "\r\n解决方案可选下列方案之一：" \
    
35.                         "\r\n    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
    
36.                         "\r\n    二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。\r\n\r\n" );
    
37. 
    
38.                 system( "pause" );
    
39.                 return (-1);
    
40.         }
    
41. 
    
42.         // 初始化
    
43.         HugeCalc::EnableTimer( TRUE );
    
44.         HugeCalc::ResetTimer();
    
45. 
    
46.         #define _COUNT__PRIME_LESS100        25
    
47. 
    
48.         UINT32 pList[_COUNT__PRIME_LESS100];
    
49.         HugeCalc::GetPrimeList( pList, _COUNT__PRIME_LESS100, 1, 100 );
    
50. 
    
51.         integer hugeProduct;
    
52.         hugeProduct.Product( CVECTOR_UINT32( pList, _COUNT__PRIME_LESS100 ) );
    
53. 
    
54.         UINT32 u32Count = 0;
    
55. 
    
56.         integer hugeResult( -1 );
    
57.         do
    
58.         {
    
59.                 ++u32Count;
    
60.                 hugeResult += hugeProduct;
    
61.         } while( !hugeResult.IsPrime() );
    
62. 
    
63.         // 暂停计时
    
64.         HugeCalc::EnableTimer( FALSE );
    
65. 
    
66.         // 输出
    
67.         printf( "%s\tλ = %u\r\nP=%s\r\n", HugeCalc::GetTimerStr(), u32Count, (LPCTSTR)hugeResult );
    
68. 
    
69.         system( "pause" );
    
70. 
    
71.         return 0;
    
72. }

复制代码

无心人

因为太容易所以要求不用大数库哦

gxqcn

在发8#时要下班了，所以比较匆忙，
该程序还可更精简的，比如 hugeProduct 仅用一条语句即可求得：hugeProduct.Primorial( 100 );

下面的程序可以分别求与在10内、100内、1000内、。。。的所有素数的同余数为(-1)的最小素数：

1. // HugeCalcDemo.cpp : Defines the entry point for the console application.
   
2. //
   
3. 
   
4. //    Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
   
5. //        Win32 Debug:    Debug Multithreaded DLL
   
6. //        Win32 Release:    Multithreaded DLL
   
7. 
   
8. #include < stdio.h >
   
9. 
   
10. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"  // 公共接口
    
11. #include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h"   // 10进制系统
    
12. #include "../../../HugeCalc_API/CppAPI/Include/HugeIntX.h"  // 16进制系统
    
13. 
    
14. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
    
15. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
    
16. 
    
17. int main(int argc, char* argv[])
    
18. {
    
19. //  printf("Hello World!\n");
    
20.     CHugeIntX hugeAdd, hugeResult;
    
21.     UINT32 n, k;
    
22. 
    
23.     printf( "Call %s\r\n", HugeCalc::GetVer());
    
24. 
    
25.     if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
    
26.     {
    
27.         printf( "\r\n警告：您未通过 HugeCalc.dll 的许可认证！\r\n" \
    
28.             "\r\n解决方案可选下列方案之一：" \
    
29.             "\r\n    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
    
30.             "\r\n    二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。\r\n\r\n" );
    
31. 
    
32.         system( "pause" );
    
33.         return (-1);
    
34.     }
    
35. 
    
36.     for ( n=10; n<=1000000; n*=10 )
    
37.     {
    
38.         // 初始化
    
39.         HugeCalc::EnableTimer( TRUE );
    
40.         HugeCalc::ResetTimer();
    
41. 
    
42.         hugeAdd.Primorial( n );
    
43.         hugeResult = -1;
    
44. 
    
45.         k = 0;
    
46.         do
    
47.         {
    
48.             ++k;
    
49.             hugeResult += hugeAdd;
    
50.         } while( !hugeResult.IsPrime() );
    
51. 
    
52.         // 暂停计时
    
53.         HugeCalc::EnableTimer( FALSE );
    
54. 
    
55.         // 输出
    
56.         printf( "%s\tP = %u*%u# - 1 = %s\r\n", HugeCalc::GetTimerStr( FT_HHMMSS_ms ), k, n,
    
57.             hugeResult.GetStrRadix( 10, NULL, FS_NORMAL ));
    
58.     }
    
59. 
    
60.     system( "pause" );
    
61. 
    
62.     return 0;
    
63. }

复制代码

不过，本题若限定仅用标准库就麻烦了，难点全在大数的素性判定上（当然大数的四则运算也是基本）。