/*最近忙于会考,刚刚看到第十二期的题目,马上想到了一个更好的方法,以下便是实践*/
/*计算二数之间有多少个素数 二数范围0到1000000*/
/*程序的精华部分在于使用了一个S[1000]数组*/
/*应该是最佳的算法了,达到了时间效率与空间效率最佳程度*/
/*Write BY S.K*/
#include<stdio.h>
#include<math.h>
unsigned char S[1000]={
0,168,135,127,120,119,114,117,107,110,112,106,103,109,105,102,108,98,104,94,104,
98,104,100,104,94,98,101,94,98,92,95,92,106,100,94,92,99,94,90,96,88,101,102,85,
96,86,90,95,89,98,89,97,89,92,90,93,99,91,90,94,88,87,88,93,80,98,84,99,80,81,98,
95,90,83,92,91,83,95,84,91,88,92,89,84,87,85,88,93,76,94,89,85,97,86,87,95,84,82,
87,87,81,93,87,80,91,82,92,76,91,88,83,84,81,88,82,93,81,90,79,87,88,86,88,88,
83,84,83,86,89,83,85,83,87,82,80,89,96,80,85,84,87,87,82,77,79,85,84,83,83,91,85,
90,88,77,84,85,76,88,77,85,85,84,81,83,77,80,81,83,73,87,87,81,89,79,83,75,95,73,
89,94,71,79,91,79,83,91,79,87,80,88,75,81,89,84,74,85,76,87,86,77,77,87,78,78,
77,83,83,87,85,88,84,86,69,81,86,74,76,80,84,91,78,80,81,80,83,84,76,80,89,88,84,
78,76,71,87,73,76,73,87,79,80,91,76,77,88,80,84,79,88,80,71,88,78,81,76,87,72,78,
86,76,77,73,79,84,80,78,87,94,75,78,84,78,83,71,80,83,83,74,81,73,87,85,77,72,
90,77,71,71,77,85,84,77,78,68,85,75,82,73,73,78,85,83,72,84,88,80,82,73,76,80,79,
69,86,86,76,77,84,84,81,86,79,80,81,71,87,85,73,86,73,81,80,82,72,81,77,77,84,80,
77,68,84,77,77,80,80,76,80,82,77,82,74,81,82,76,87,79,67,80,83,71,68,79,76,84,
77,77,85,79,72,68,70,76,81,73,82,85,80,71,77,83,72,76,74,81,78,80,78,69,75,84,81,
79,86,87,75,72,75,75,82,81,70,71,76,75,70,83,67,81,79,82,73,81,74,69,90,80,67,82,
85,75,75,73,77,83,81,74,71,78,71,89,76,79,84,80,85,82,73,70,75,75,79,72,85,88,82,
68,68,73,70,80,92,76,63,72,74,82,73,77,75,68,77,69,74,77,85,74,69,83,85,72,87,78,
73,78,80,86,75,69,85,71,77,78,82,75,65,63,82,78,83,78,78,76,67,82,80,87,68,81,72,
81,79,74,67,76,76,83,76,71,76,75,72,82,70,77,81,66,85,83,76,78,73,83,79,69,77,79,
84,72,70,78,80,68,79,74,72,71,87,67,78,71,73,77,78,81,68,69,73,76,77,78,79,75,71,
80,77,61,88,68,74,77,86,61,83,67,77,78,72,72,71,80,85,72,85,72,70,77,78,77,76,77,
73,79,73,78,72,81,79,87,73,68,71,67,80,77,78,77,79,73,72,73,76,73,83,76,
73,74,72,78,78,80,73,71,76,79,71,75,85,81,67,73,77,70,74,75,78,69,70,70,71,75,67,
81,77,70,82,78,73,74,59,72,77,71,68,70,86,75,74,79,73,84,61,74,85,69,78,73,71,70,
79,73,83,70,74,77,77,77,73,74,66,74,75,76,76,77,73,75,74,63,82,83,75,78,66,78,72,
74,74,82,74,79,60,79,77,73,76,77,73,79,62,72,75,71,81,71,87,68,82,74,77,77,78,76,
72,73,66,83,69,65,67,74,78,77,73,86,75,69,76,75,76,75,69,76,71,75,74,79,69,78,70,
81,67,74,73,67,64,67,76,71,76,72,68,85,73,71,83,70,66,68,79,77,77,80,68,79,72,82,
78,68,77,74,77,75,70,76,72,67,70,76,81,71,70,82,68,75,75,77,70,73,80,68,78,71,82,
71,73,79,77,72,71,71,85,66,70,69,78,79,68,70,69,78,78,72,69,72,78,69,75,75,62,83,
75,72,84,78,71,81,78,69,69,68,76,79,82,68,67,73,71,64,80,69,70,69,83,68,
78,70,69,77,75,68,70,77,74,66,71,73,78,76,69,71,77,74,83,60,80,80,68,78,80,73,79,
58,76,65,75,80,75,67,78,75,80,69,72,73,69,77,76,71,77,68,68,80,69,72,74,80,64,75,
76,61,74,73,70,63,81,70,80,80,79,82,62,81,71,54,73,70,72,79,75,71,72,72,72,81,
76,80,74,63,70,80,69,69,76,68,81,68,71,71,72,68,74,79,72,76,73,66,72,66,67,75,76,
70,78,65,73,76,58,69,77,69,68,88,71,74,74,70,73,66,75,73,76,78,74,63,85,70,66,60,
80,65,67,75,70,70,70,76,76,63,71,72,71,79,65,68,78,69,69,83,74};
long m=0;
long n1,n2;
long i,k;
void sumx(long n1,long n2)
{
for(i=n1;i<n2;i++)
{
m++;
for(k=2;k<=sqrt(i);k++)
if(i%k==0)
{
m--;
break;
}
}
}
int main(void)
{
scanf("%ld%ld",&n1,&n2);
if(n1/1000!=n2/1000)
{
for(i=n1/1000+2;i<=n2/1000;i++) m+=S[i];
sumx(n1,(n1/1000+1)*1000);
sumx(n2/1000*1000,n2+1);
}
else
sumx(n1,n2+1);
if(n1==1) m--;
printf("%ld",m);
getch();
return 0;
}
