用计算机编程的方法证明2^67-1不是素数 - 编程论坛

#2

幻紫灵心2018-12-13 12:34

插个眼

#3

rjsp2018-12-13 12:41

写个大数除法的函数

#4

powerfrank2018-12-13 16:49

回复 3楼 rjsp

2的67次方的值位数有21位，如果2^67-1不是素数，分解为两数相乘，其中较小值的最大的可能能达到10位，较大值的最小的可能能达到11位。用除法得到的结果不会有数据溢出？
我是倾向于用加法然后再比较，但是考虑到循环一次就要加10000 00000次，我有点头大。

#5

幻紫灵心2018-12-13 17:42

2^67 - 1 = 147573952589676412927 = 761838257287 × 193707721
大数循环遍历1.9亿次肯定可以弄出来的，计算机又不会累，但是没啥技术含量啊.
数学方法嘛...梅森素数数学界大佬也是用很多年才证明这个不是素数，。

#6

wlxy_wang2018-12-14 15:53

这个问题的核心就是你怎么把2^67-1精确的表示出来，并能进行数学运算，其他的都很简单了
https://blog.
这是个大数算法，看看吧

[此贴子已经被作者于2018-12-14 16:03编辑过]

#7

花花花花花2018-12-15 20:20

想问一下怎么关注帖子啊？？

#8

rjsp2018-12-17 13:20

以下是引用powerfrank在2018-12-13 16:49:59的发言：

2的67次方的值位数有21位，如果2^67-1不是素数，分解为两数相乘，其中较小值的最大的可能能达到10位，较大值的最小的可能能达到11位。用除法得到的结果不会有数据溢出？
我是倾向于用加法然后再比较，但是考虑到循环一次就要加10000 00000次，我有点头大。

效率不高，需要六秒多出结果

程序代码：

#include <stdio.h>

// 余数 mydiv( 被除数, 除数, 商 )
unsigned long long mydiv( const unsigned numerator[], unsigned long long denominator, unsigned quotient[] )
{
    unsigned long long remainder = 0;

    for( size_t i=0; i!=3; ++i )
    {
        remainder = remainder*1000000000 + numerator[i];
        quotient[i] = (unsigned)(remainder/denominator);
        remainder %= denominator;
    }

    return remainder;
}

int mycompare( const unsigned a[], unsigned long long b )
{
    unsigned b_[] = { (unsigned)(b/1000000000000000000), (unsigned)(b%1000000000000000000/1000000000), (unsigned)(b%1000000000) };
    for( size_t i=0; i!=3; ++i )
    {
        if( a[i] < b_[i] ) return -1;
        if( a[i] > b_[i] ) return +1;
    }
    return 0;
}

void myprint( const unsigned a[] )
{
    if( a[0] != 0 )
        printf( "%u%09u%09u", a[0], a[1], a[2] );
    else if( a[1] != 0 )
        printf( "%u%09u", a[1], a[2] );
    else
        printf( "%u", a[2] );
}

int main( void )
{
    const unsigned n[] = { 147, 573952589, 676412927 }; // 2^67-1

    for( unsigned long long denom=3; ; denom+=2 )
    {
        unsigned quotient[3];
        unsigned long long remainder = mydiv( n, denom, quotient );

        if( remainder == 0 )
        {
            printf( "%llu * ", denom );
            myprint( quotient );
            putchar( '\n' );
            break;
        }

        if( mycompare(quotient,denom) < 0 )
        {
            puts( "it is a prime number." );
            break;
        }
    }
}

输出

193707721 * 761838257287