素数个数解决思路

素数个数
求a,b之间的素数个数

每行输入a和b（0<=a,b<=500000）

每行输出包括a和b在内的素数个数

Sample Input
0 3
5 296
9 9

Sample Output
2
60
0

------解决方案--------------------
#include <iostream>
#include <algorithm>
using namespace std;
bool prime(int Number);
int main( )
{
while(true)
{
int a,b,sum=0;
cout<<"please input two number:";
cin >> a >> b;
if(max(a,b)<=50000&&0<=min(a,b)){
int i;
if(min(a,b)<2)
{
i=2;
}
else
{
i=min(a,b);
}
for(i; i <= max(a,b); i++)
{
if (prime(i))
{
sum++;
}

}
cout<<sum<<endl;
}
}

return 0;
}
bool prime(int Number)
{
//（在此补充）
int i;
for(i=2;i*i<=Number;++i)
if(Number%i==0)
return false;
return true;
}
------解决方案--------------------

C/C++ code


#include <stdio.h>

int isprime(unsigned long n)
{
    unsigned long i;

    if(n == 1 || n == 2 || n == 3 || n == 5)
    {
        return 0;
    }
    else if(n % 2)
    {
        for(i = 3; i <= n / 2 + 1; i += 2)
        {
            if(n % i == 0)
            {
                return -1;
            }
        }
        return 0;
    }
    else
    {
        return -1;
    }
}

unsigned long count_prime(unsigned long m, unsigned long n)
{
    unsigned count = 0;
    unsigned long i;

    for(i = m; i <= n; i++)
    {
        if(isprime(i) == 0)        
        {
            count++;
        }
    }

    return count;
}

int main(int argc, char* argv[])
{
    unsigned long m;
    unsigned long n;

    do{
        scanf("%lu %lu", &m, &n);
        printf("%lu\n", count_prime(m, n));
    }while(m != 0 || n != 0);

    return 0;
}

素数个数解决思路

相关推荐