Erastothenes C ++ SPOJ分段筛 [英] Segmented Sieve of Erastothenes C++ SPOJ

问题描述

我知道这之前已被问过，但我不能完全了解如何实施Eratosthenes的细分筛选。

问题 / p>

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

strong>我的方法

我可以实现筛选Eratosthenes，我可以找到到n的平方根的素数。
但是我不能理解如何实现在其他网站上讨论的偏移。如何在所选分区上执行筛选？

  #include< stdio.h> 
 #include< iostream> 
 #include< math.h> 
 using namespace std; 
 
 int main（）
 {
 int t; 
 cin>> t; 
 
 while（t--）
 {
长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  primes [i] = true; 
 
 for（i = 2; i <= square; i ++）
 {
 if（primes [i] == true）
 {
 （j = i + i; j <= n; j + = i）
 primes [j] = false; 
} 
} 
 
 for（i = m; i  {
 if（primes [i] == true）
 {
 cout<< i<<\t; 
 if（i> = m）
 {
 p [j] = i; 
 j ++; 
} 
} 
} 
 
 for（i = 0; i  {
 cout< i]<<\ n; 
} 
} 
 
 return 0; 
} 
  

解决方案

a，b]和一个素数p。

请注意，下面的代码将会消除所有与p对应的复合数据。

  for（int i = ceil（a / p）; i <= floor（b / p）; ++ i）{
 new_primes [i * pa ] = false;对于所有素数，扩展这个想法< =  sqrt（b）
 
 
 。
 
I'm aware this has been asked before, but I cannot fully understand how to implement Segmented Sieve of Eratosthenes.

Problem

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space. For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

My approach

I could implement Sieve of Eratosthenes and I can find prime numbers up to square root of n.
But I'm not able to understand how to implement the "offset" that is being discussed on other sites. How to perform a Sieve on a selected partition?
#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;
}

解决方案
Consider a segment S : [a,b] and a prime p.

Note that the following code will eliminate all composites "corresponding" to prime p.
for(int i=ceil(a/p);i<=floor(b/p);++i) {
    new_primes[i*p-a]=false;
Extend this idea for all primes <= sqrt(b).

                        
这篇关于Erastothenes C ++ SPOJ分段筛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！