素数判定

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 56842    Accepted Submission(s): 19531


Problem Description
对于表达式n^2+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x<y<=50)，判定该表达式的值是否都为素数。
 

Input
输入数据有多组，每组占一行，由两个整数x，y组成，当x=0,y=0时，表示输入结束，该行不做处理。
 

Output
对于每个给定范围内的取值，如果表达式的值都为素数，则输出"OK",否则请输出“Sorry”,每组输出占一行。
 

Sample Input
0 1
0 0
 

Sample Output
OK
 

#include <iostream>
#include <math.h>
using namespace std;
int main()
{
    int x,y,j,k;
    while(cin>>x>>y)
    {
        if(x==0 && y==0)
            break;
        for(x; x<=y ;++x)
        {    k=1;
             j=x*x+x+41;
            for(int i=2;i<=(sqrt(j)); i++)
            { 
                if(j%i==0)
                {
                    k=0;
                    break;
                }
            }
            if(k==0)
                break;
        }
        if(k==0)
            cout<<"Sorry"<<endl;
        else
            cout<<"OK"<<endl;
    }
    return 0;
}

这是什么错误

View Compilation Error

0_0_8856365_32655.cpp
0_0_8856365_32655.cpp(15) : error C2668: “sqrt” : 对重载函数的调用不明确
        \include\math.h(626): 可能是“long double sqrt(long double)”
        \include\math.h(578): 或       “float sqrt(float)”
        \include\math.h(200): 或       “double sqrt(double)”
        试图匹配参数列表“(int)”时

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

+1

对于表达式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 编辑 ]

假设是合数，则有 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 编辑 ]

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

#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 编辑 ]

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

对于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版