寻找最小素数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. //
4. // Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
5. // Win32 Debug: Debug Multithreaded DLL
6. // Win32 Release: Multithreaded DLL
8. #include <stdio.h>
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进制系统
14. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
15. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
17. #if 1
18. #define _Test_HI
19. #define integer CHugeInt
20. #else
21. #define _Test_HX
22. #define integer CHugeIntX
23. #endif
25. int main(int argc, char* argv[])
26. {
27. // printf("Hello World!\n");
29. printf( "Call %s\r\n", HugeCalc::GetVer());
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" );
38. system( "pause" );
39. return (-1);
40. }
42. // 初始化
43. HugeCalc::EnableTimer( TRUE );
44. HugeCalc::ResetTimer();
46. #define _COUNT__PRIME_LESS100 25
48. UINT32 pList[_COUNT__PRIME_LESS100];
49. HugeCalc::GetPrimeList( pList, _COUNT__PRIME_LESS100, 1, 100 );
51. integer hugeProduct;
52. hugeProduct.Product( CVECTOR_UINT32( pList, _COUNT__PRIME_LESS100 ) );
54. UINT32 u32Count = 0;
56. integer hugeResult( -1 );
57. do
58. {
59. ++u32Count;
60. hugeResult += hugeProduct;
61. } while( !hugeResult.IsPrime() );
63. // 暂停计时
64. HugeCalc::EnableTimer( FALSE );
66. // 输出
67. printf( "%s\tλ = %u\r\nP=%s\r\n", HugeCalc::GetTimerStr(), u32Count, (LPCTSTR)hugeResult );
69. system( "pause" );
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. //
4. // Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
5. // Win32 Debug: Debug Multithreaded DLL
6. // Win32 Release: Multithreaded DLL
8. #include < stdio.h >
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进制系统
14. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
15. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
17. int main(int argc, char* argv[])
18. {
19. // printf("Hello World!\n");
20. CHugeIntX hugeAdd, hugeResult;
21. UINT32 n, k;
23. printf( "Call %s\r\n", HugeCalc::GetVer());
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" );
32. system( "pause" );
33. return (-1);
34. }
36. for ( n=10; n<=1000000; n*=10 )
37. {
38. // 初始化
39. HugeCalc::EnableTimer( TRUE );
40. HugeCalc::ResetTimer();
42. hugeAdd.Primorial( n );
43. hugeResult = -1;
45. k = 0;
46. do
47. {
48. ++k;
49. hugeResult += hugeAdd;
50. } while( !hugeResult.IsPrime() );
52. // 暂停计时
53. HugeCalc::EnableTimer( FALSE );
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. }
60. system( "pause" );
62. return 0;
63. }

复制代码

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