首页 文章

Erastothenes C SPOJ的分段筛[重复]

提问于
浏览 次
-1

这个问题在这里已有答案：

我知道之前已经问过这个问题，但是我无法完全理解如何实现Eratosthenes的分段筛 .

Problem

输入以单行中的测试用例数t开始（t <= 10） . 在接下来的t行中的每一行中，存在由空格分隔的两个数m和n（1 <= m <= n <= 1000000000，n-m <= 100000） . 对于每个测试用例，打印所有质数p，使得m <= p <= n，每行一个数，由空行分隔的测试用例 .

My approach

我可以实现Eratosthenes的Sieve，我可以找到n的平方根的素数 . 但我无法理解如何实现其他网站上讨论的“偏移” . 如何在选定的分区上执行Sieve？

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int t;
    cin>>t;

    while(t--)
    {
        long long m,n;
        long long p[100001];
        bool primes[100000];

        cin>>m;
        cin>>n;
        long long square=sqrt(n);
        cout<<square;
        int j=0;
        int i;
        primes[0]=false;    
        primes[1]=false;

        for(i=2; i<n;i++)
            primes[i]=true;

        for(i=2; i<=square; i++)
        {
            if(primes[i]==true)
            {
                for(j=i+i; j<=n; j+=i)
                    primes[j]=false;
            }
        }

        for(i=m; i<n ; i++)
        {
            if(primes[i]==true)
            {
                cout<<i<<" \t";
                if(i >= m)
                {
                    p[j]=i;
                    j++;
                }
            }
        }

        for(i=0 ; i<j ; i++)
        {
            cout<<p[i]<<"\n";
        }
    }

    return 0;
}
c++ primes sieve-of-eratosthenes

2 回答

  • 1

    首先，既然你提到你正在为SPOJ编码，我会告诉你这不会起作用 . 即使你以某种方式得到一个从m到n做SOE的方法，你也会进行t次这样的seof，这会给你TLE .

    所考虑的是在整个范围内的简单的SOE预计算，即从1到10 ^ x . 首先在while循环之外执行SOE并将所有素数存储到向量中 . 然后在while循环中，只需从向量中显示所需的素数 .

    回复于
  • 0

    考虑段S：[a，b]和素数p .

    请注意，以下代码将消除与prime p“对应”的所有复合 .

    for(int i=ceil(a/p);i<=floor(b/p);++i) {
    new_primes[i*p-a]=false;

    为所有素数<= sqrt(b) 扩展这个想法 .

    回复于

相关问题