一个数如果满足以下全部条件的话,那么这个数便是滋润数。
- a为正整数
- 区间[a,2a]内至少有一个素数
- (((a*307829558302172+9317635829295)%56323)+18)%17=1成立 现在夏吉巴先生想知道,在区间[1,n]内有多少个滋润数。 Input 输入的第一行为t(1<=t<=10000),表示有t组数据。 接下来有t行,每行为一组数据,仅包含一个整数n(2<=n<=1,000,000,000,000,000,000)
Output
对于每组数据,输出区间[1,n]内的滋润数的个数。
代码如下,多多指教!
int Is_prime(int a);
int main()
{
int t,n,a,r,j,sum=0;
while(scanf("%d\n",& t)!=EOF)
{
while(t--)
{
scanf("%d",& n);
if(n>0)
{
for( j=1;j<=n;j++)
{
while(j<=2*j)
{
if(Is_prime(j))
{
r=1;
break;
}
else r=0;
}
if(r==1 && (((j*307829558302172+9317635829295)%56323)+18)%17==1)
sum+=1;
}
printf("%d\n\n",sum);
sum=0;
}
}
}
return 0;
}
int Is_prime(int a)
{
for(int i=2;i<sqrt(a);i++)
{
if(a%i==0) {return 0;}
}
return 1;
}