一开始稀里糊涂的WA了1次,发现自己还在用最朴素的判素方法,QAQ,,,然后果断想起了一种更加快速的判素方法,,那就是 筛选法,
其实筛选法的原理很简单,只要我们认真的手模一遍就能发现规律了~打表——>查表,OK~AC、、、
切记,以后再出现小数据的判素题目,就用筛选法了~
# include<cstdio> # include<iostream> # include<cstring> using namespace std; # define MAX 2700 int hash[MAX]; void dabiao() { memset( hash,0,sizeof(0) ); hash[0] = 1; hash[1] = 1; for ( int i = 2;i < MAX;i++ ) { if ( ~hash[i] ) for ( int j = 2*i;j < MAX;j+=i ) { hash[j] = 1; } } } int main(void) { dabiao(); int n,m; while ( cin>>n>>m ) { int flag = 0; if ( n==0&&m==0 ) break; for ( int i = n;i <= m;i++ ) { if ( hash[i*i+i+41] ) { flag = 1; break; } } if ( flag ) cout<<"Sorry"<<endl; else cout<<"OK"<<endl; } return 0; }