论坛 › 编程擂台 › 寻找最小素数P，满足如下条件

无心人 发表于 2008-6-26 16:03:10

寻找最小素数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 发表于 2008-6-26 16:34:23

$p_1$是什么？2？

mathe 发表于 2008-6-26 16:36:40

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

无心人 发表于 2008-6-26 16:39:05

素数阿

老大

mathe 发表于 2008-6-26 16:41:50

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

mathe 发表于 2008-6-26 16:42:53

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

无心人 发表于 2008-6-26 16:43:00

:lol

呵呵，公式都出来了阿

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

gxqcn 发表于 2008-6-26 17:08:01

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

代码如下：// HugeCalcDemo.cpp : Defines the entry point for the console application.
//

//        Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
//                Win32 Debug:        Debug Multithreaded DLL
//                Win32 Release:        Multithreaded DLL

#include <stdio.h>

#include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"        // 公共接口
#include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h"        // 10进制系统
#include "../../../HugeCalc_API/CppAPI/Include/HugeIntX.h"        // 16进制系统

#pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )

#if 1
        #define _Test_HI
        #define integer CHugeInt
#else
        #define _Test_HX
        #define integer CHugeIntX
#endif

int main(int argc, char* argv[])
{
//        printf("Hello World!\n");

        printf( "Call %s\r\n", HugeCalc::GetVer());

        if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
        {
                printf( "\r\n警告：您未通过 HugeCalc.dll 的许可认证！\r\n" \
                        "\r\n解决方案可选下列方案之一：" \
                        "\r\n    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
                        "\r\n    二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。\r\n\r\n" );

                system( "pause" );
                return (-1);
        }

        // 初始化
        HugeCalc::EnableTimer( TRUE );
        HugeCalc::ResetTimer();

        #define _COUNT__PRIME_LESS100        25

        UINT32 pList;
        HugeCalc::GetPrimeList( pList, _COUNT__PRIME_LESS100, 1, 100 );

        integer hugeProduct;
        hugeProduct.Product( CVECTOR_UINT32( pList, _COUNT__PRIME_LESS100 ) );

        UINT32 u32Count = 0;

        integer hugeResult( -1 );
        do
        {
                ++u32Count;
                hugeResult += hugeProduct;
        } while( !hugeResult.IsPrime() );

        // 暂停计时
        HugeCalc::EnableTimer( FALSE );

        // 输出
        printf( "%s\tλ = %u\r\nP=%s\r\n", HugeCalc::GetTimerStr(), u32Count, (LPCTSTR)hugeResult );

        system( "pause" );

        return 0;
}

无心人 发表于 2008-6-26 17:18:00

:)

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

gxqcn 发表于 2008-6-26 19:05:27

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

下面的程序可以分别求与在10内、100内、1000内、。。。的所有素数的同余数为(-1)的最小素数：// HugeCalcDemo.cpp : Defines the entry point for the console application.
//

//    Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
//      Win32 Debug:    Debug Multithreaded DLL
//      Win32 Release:    Multithreaded DLL

#include < stdio.h >

#include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"// 公共接口
#include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h"   // 10进制系统
#include "../../../HugeCalc_API/CppAPI/Include/HugeIntX.h"// 16进制系统

#pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )

int main(int argc, char* argv[])
{
//printf("Hello World!\n");
    CHugeIntX hugeAdd, hugeResult;
    UINT32 n, k;

    printf( "Call %s\r\n", HugeCalc::GetVer());

    if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
    {
      printf( "\r\n警告：您未通过 HugeCalc.dll 的许可认证！\r\n" \
            "\r\n解决方案可选下列方案之一：" \
            "\r\n    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
            "\r\n    二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。\r\n\r\n" );

      system( "pause" );
      return (-1);
    }

    for ( n=10; n<=1000000; n*=10 )
    {
      // 初始化
      HugeCalc::EnableTimer( TRUE );
      HugeCalc::ResetTimer();

      hugeAdd.Primorial( n );
      hugeResult = -1;

      k = 0;
      do
      {
            ++k;
            hugeResult += hugeAdd;
      } while( !hugeResult.IsPrime() );

      // 暂停计时
      HugeCalc::EnableTimer( FALSE );

      // 输出
      printf( "%s\tP = %u*%u# - 1 = %s\r\n", HugeCalc::GetTimerStr( FT_HHMMSS_ms ), k, n,
            hugeResult.GetStrRadix( 10, NULL, FS_NORMAL ));
    }

    system( "pause" );

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

查看完整版本: 寻找最小素数P，满足如下条件