1007      阿里云  技术社区[云栖]

筛法求素数

#include <iostream>
#include <vector>
using namespace std;

#define MAX_LEN 1000000
void getPrimeTable(bool *prime);

int main()
{
    bool prime[MAX_LEN+1];
    long a, b;
    long i;
    vector<long> vec;//由于数可能很大
    long t;

    getPrimeTable(prime);

    while (cin >> a >> b)
    {
        t = 0;
        for (i = a; i <= b; i++)
        {
            if (prime[i] == true)
            {
                t ++;
            }
        }
        vec.push_back(t);
    }
    i = 1;
    for (vector<long>::iterator it = vec.begin(); it != vec.end(); it++)
    {
        cout << "Case " << i << ":" << endl;
        cout << *it << endl;
    }

    return 0;
}

void getPrimeTable(bool *prime)
{
    long i, j;

    for (i = 2; i <= MAX_LEN; i++)
    {
        prime[i] = true;
    }
    prime[0] = prime[1] = false;

    for (i = 2; i <= MAX_LEN; i++)
    {
        if (prime[i] == true)
        {
            for (j = 2 * i; j <= MAX_LEN; j += i)
            {
                prime[j] = false;
            }
        }
    }
}

最后更新：2017-04-02 15:15:28

  上一篇： 一百万以内的素数

  下一篇： 蛮力法找假金币