Luogu 1835 素數密度 區間埃式篩

• • • • • 傳送門
        • 思路
        • 參考代碼
          • 歐拉篩
          • 埃式篩

傳送門

思路

  使用傳說中的區間埃式篩。

  可以知道，如果 [l,r] [ l , r ] 中的某個數是合數，那麼它的一個質因子一定 ≤r√ ≤ r 。是以可以使用埃式篩先篩出 [1,r√] [ 1 , r ] 的所有素數，再用這些素數去篩區間中的合數。

  雖然按道理歐拉篩比埃式篩在第一步中時間複雜度更占優勢，但是第一步最多隻會算到四萬多，歐拉篩常數較大，反而比較慢。

  第二步隻能用埃式篩。

參考代碼

  關鍵代碼是

unsigned int j = prime[i] * std::max(2, ((l + prime[i] - 1) / prime[i]));

，要注意類型。

歐拉篩

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
typedef int INT;
using std::cin;
using std::cout;
using std::endl;
INT readIn()
{
    INT a = ;
    bool minus = false;
    char ch = getchar();
    while (!(ch == '-' || (ch >= '0' && ch <= '9'))) ch = getchar();
    if (ch == '-')
    {
        minus = true;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        a = a *  + (ch - '0');
        ch = getchar();
    }
    if (minus) a = -a;
    return a;
}
void printOut(INT x)
{
    char buffer[];
    INT length = ;
    if (x < )
    {
        putchar('-');
        x = -x;
    }
    do
    {
        buffer[length++] = x %  + '0';
        x /= ;
    } while (x);
    do
    {
        putchar(buffer[--length]);
    } while (length);
}

const int maxn = int() + ;
int l, r;

const int maxm = ;
int prime[maxm];
bool isntPrime[maxm];
int sqrtR;
void init()
{
    for (int i = ; i <= sqrtR; i++)
    {
        if (!isntPrime[i])
            prime[++prime[]] = i;
        for (int j = , s = i * prime[j]; j <= prime[] && s <= sqrtR; j++, s = i * prime[j])
        {
            isntPrime[j] = true;
            if (!(i % prime[j]))
                break;
        }
    }
}

bool is[maxn];
void run()
{
    l = readIn();
    r = readIn();
    sqrtR = std::sqrt(r);
    init();

    for (int i = ; i <= prime[]; i++)
        for (unsigned int j = prime[i] * std::max(, ((l + prime[i] - ) / prime[i])); j <= r; j += prime[i])
            is[j - l] = true;

    int ans = ;
    for (int i = , to = r - l + ; i < to; i++)
        ans += !is[i];
    printOut(ans);
}

int main()
{
    run();
    return ;
}
           

埃式篩

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
typedef int INT;
using std::cin;
using std::cout;
using std::endl;
INT readIn()
{
    INT a = ;
    bool minus = false;
    char ch = getchar();
    while (!(ch == '-' || (ch >= '0' && ch <= '9'))) ch = getchar();
    if (ch == '-')
    {
        minus = true;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        a = a *  + (ch - '0');
        ch = getchar();
    }
    if (minus) a = -a;
    return a;
}
void printOut(INT x)
{
    char buffer[];
    INT length = ;
    if (x < )
    {
        putchar('-');
        x = -x;
    }
    do
    {
        buffer[length++] = x %  + '0';
        x /= ;
    } while (x);
    do
    {
        putchar(buffer[--length]);
    } while (length);
}

const int maxn = int() + ;
int l, r;

const int maxm = ;
int sqrtR;

bool isntPrime1[maxm];
bool isntPrime2[maxn];

void run()
{
    l = readIn();
    r = readIn();
    sqrtR = std::sqrt(r);

    for (int i = ; i <= sqrtR; i++)
    {
        if (!isntPrime1[i])
        {
            for (int j = i * i; j <= sqrtR; j += i)
                isntPrime1[j] = true;
            for (unsigned int j = std::max(, (l + i - ) / i) * i; j <= r; j += i)
                isntPrime2[j - l] = true;
        }
    }

    int ans = ;
    for (int i = , to = r - l + ; i < to; i++)
        ans += !isntPrime2[i];
    printOut(ans);
}

int main()
{
    run();
    return ;
}