数素数C/C++

Description

素数是的只能被1和它本身整除的自然数。判断一个数是素数的方法是使用2到该数的平方根的素数除它，若有能整除的则该数不是素数。

Input

本题有多组数据，每组数据由两个正整数M,N组成。（0＜M＜N＜1000000）

Output

输出一个整数，表示介于M,N之间（包括M,N）的素数的数量。

Sample Input

5 10
1 3
6 8

Sample Output

2
2
1

不能用2到sqr(x)之间的数去除是否能整除
因为当为1--1000000时要的时间很长

只能用“断一个数是素数的方法是使用2到该数的平方根的素数除它，若有能整除的则该数不是素数。”的方法。

麻烦各位大侠贴出正确的代码，用C或C++
Time Limit:1000MS Memory Limit:65536K

有一种无赖的方法:
事先算好各区间的素数个数
1~10万 n0个
10~20万 n1个
.
.
.
90~100万 n9个
如果m,n分别落在不同的区间
m=i*10万 + r
n=j*10万 + s
f(m,n) = f(m, (i+1)*10万) + n(i+1) + ... n(j-1) + f(j*10万,n)

//稍稍改进判断素数
bool isprime(int n)
{
if(n==2)return true;
if(n==1)return false;
if(n%2==0)return false;
for (int i=3;i<=sqrt(n);i=i+2)
{
if(n%i==0)return false;
}
return true;
}

void print(int m, int n)
{
int k=0;
if (m==1 || m==2)
{
k=1;
m=3;
}
if(m%2==0)m=m+1;
while (m<=n)
{
if(isprime(m))k++;
m+=2;
}
cout<<k<<endl;
}

#include"stdio.h"
#include"math.h"
int fun(int n)
{
double i;
int j;
if(n<=1)
return 0;
else if(n==2)
return 1;
else if(n%2==0)
return 0;
else if(n%3==0&&n!=3)