hud 2012 题素数判定求解哪里错了？

#2

rjsp2013-08-07 13:26

只说你的代码
sort 有三种重载形式，分别是
float sqrt(float)
double sqrt(double)
long double sqrt(long double)
而你的代码中传给sqrt的参数类型是int，编译器不知道你想要哪个重载

#3

peach54602013-08-07 13:34

以下是引用rjsp在2013-8-7 13:26:15的发言：

只说你的代码
sort 有三种重载形式，分别是
float sqrt(float)
double sqrt(double)
long double sqrt(long double)
而你的代码中传给sqrt的参数类型是int，编译器不知道你想要哪个重载

+1

#4

rjsp2013-08-07 13:34

对于表达式n^2+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x<y<=50)
--- 也就是表达式的值范围是 [41,2591]，求这个范围的素数

n^2+n+41
--- [(n+1)^2+(n+1)+41] - [n^2+n+41] = 2*(n+1)

[ 本帖最后由 rjsp 于 2013-8-7 14:42 编辑 ]

#5

rjsp2013-08-07 14:02

假设是合数，则有 n^2+n+41 == (n+a)(n+b)
n^2+n+41 == n^2 + (a+b)n + ab
即 n = (41-ab)/(a+b-1)
如果a+b等于1，这个公式是无意义的，假设a+b==1，则 n^2+n+41 == n^2 + n + ab => ab=41，而a+b=1且ab=41是无解的（一元二次方程delta小于0）
现在只有避开 n == (41-ab)/(a+b-1) 的整数解就行了

[ 本帖最后由 rjsp 于 2013-8-7 14:12 编辑 ]

#6

rjsp2013-08-07 14:46

用的是最简单的方法（因为这代码最好写^_^），先求素数列表

程序代码：

#include <iostream>
using namespace std;

int main()
{
    // -39<=n<=50 n^2+n+41
    // (+50)*(+50)+(+50)+41 = 2591
    // 2591^0.5 = 50
    bool mask[2592] = { false }; // true为合数
    for( size_t i=2; i<=50; ++i )
    {
        if( mask[i] )
            continue;
        for( size_t j=i+i; j<2592; j+=i )
            mask[j] = true;
    }

    for( int x,y; cin>>x>>y && !(x==0 && y==0); )
    {
        for( ; x<=y && !mask[x*x+x+41]; ++x );
        cout << (x>y?"OK":"Sorry") << endl;
    }

    return 0;
}

还可以将 x*x+x+41 先算掉

程序代码：

#include <iostream>
using namespace std;

int main()
{
    // 先求素数表
    // -39<=n<=50 n^2+n+41
    // (+50)*(+50)+(+50)+41 = 2591
    // 2591^0.5 = 50
    bool mask[2592] = { false }; // true为合数
    for( size_t i=2; i<=50; ++i )
    {
        if( mask[i] )
            continue;
        for( size_t j=i+i; j<2592; j+=i )
            mask[j] = true;
    }

    // 再求-39到50中哪些数行，哪些数不行
    bool table[90]; // 索引从-39开始
    for( int n=-39; n<=50; ++n )
        table[n+39] = mask[n*n+n+41];

    for( int x,y; cin>>x>>y && !(x==0 && y==0); )
    {
        for( ; x<=y && !table[x+39]; ++x );
        cout << (x>y?"OK":"Sorry") << endl;
    }

    return 0;
}

甚至直接写成

程序代码：

#include <iostream>

int main()
{
    for( int x,y; cin>>x>>y && !(x==0 && y==0); )
        std::cout << ( ( y<=39 || (x>=42 && y<=43) || (x>=45 && y<=48) || x>=50 ) ? "OK" : "Sorry" ) << std::endl;

    return 0;
}

[ 本帖最后由 rjsp 于 2013-8-7 15:09 编辑 ]

#7

love云彩2013-08-08 09:49

以下是引用rjsp在2013-8-7 13:26:15的发言：

只说你的代码
sort 有三种重载形式，分别是
float sqrt(float)
double sqrt(double)
long double sqrt(long double)
而你的代码中传给sqrt的参数类型是int，编译器不知道你想要哪个重载

怎么解决楼主这个问题？新手求教呀

#8

rjsp2013-08-08 10:47

回复 7楼 love云彩

对于C++，强制转化一下，如下
sqrt( float(j) )
sqrt( double(j) )
sqrt( long double(j) )
但强制转化写起来不好看，所以还可以用如下进行隐式提升方法
sqrt( j*1.0f )
sqrt( j*1.0 )
sqrt( j*1.0L )

对于C，是没有函数重载的，因此可以直接写成
sqrtf( j )
sqrt( j )
sqrtfl( j )

#9

szgg5202013-08-08 12:01

楼上是明白人．．．．

#10

love云彩2013-08-08 13:41

以下是引用rjsp在2013-8-8 10:47:18的发言：

对于C++，强制转化一下，如下
sqrt( float(j) )
sqrt( double(j) )
sqrt( long double(j) )
但强制转化写起来不好看，所以还可以用如下进行隐式提升方法
sqrt( j*1.0f )
sqrt( j*1.0 )
sqrt( j*1.0L )

对于C，是没有函数重载的，因此可以直接写成
sqrtf( j )
sqrt( j )
sqrtfl( j )

受教啦，谢谢R版

hud 2012 题 素数判定 求解哪里错了？