java - Eratosthenes 分段筛法 - Java

Question

所以我尝试用 Java 实现埃拉托色尼分段筛法，这是我能做的最好的。当我运行它时，它没有给出任何错误，但它没有返回任何东西，尽管我在末尾添加了“System.out.println”以打印出所有剩余的素数。提前感谢您的建议

public class SegmentedSieveofEratosthenes  {

public static void main(String[] args) throws java.lang.Exception {
    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int m = in.nextInt();
    boolean[] v = new boolean[1000000];
    int[] primes = new int[1000000];
    //counter for the primes vector
    int counter = 0;

    for(int i=2;i<=(int)Math.sqrt(m);i++)
    {
        v[i]=true;
    }

    for(int i=2;i<=(int)Math.sqrt(m);i++)
    {
        if(v[i]=true)
        {
            primes[counter]=i;
            counter=counter+1;
            for(int j=i+1;j<=(int)Math.sqrt(m);j++)
            {
                if(j%i==0)
                {
                    v[j]=false;
                }
            }
        }
    }

    boolean[] flags = new boolean[1000000];
    for(int i=n;i<=m;i++)
    {
        flags[i]=true;
    }

    for(int i=0;i<counter;i++)
    {
        int start = (n/primes[i])*3;
        for(int j=start+i;j<=m;j=j+i)
            flags[j]=false;
    }

    for(int i=n;i<=m;i++)
        if(flags[i]==true)
            System.out.println(i);

    in.close();
    }
  }

Answer 1

您的实现存在三个明显的问题。第一个问题是您在条件中将 v[i] 分配给 true

if(v[i]=true)

然后在for循环的终止条件中出现了一些差一错误，特别是

for (...; i<=m; ...)

代替

for (...; i<m; ...)

最后，您的数学计算出了以下问题

int start = (n/primes[i])*3;
for(int j=start+i;j<=m;j=j+i)
    flags[j]=false;

我确定这是一个小修复，但我想不出来所以我自己写了

int start = n + (-n % primes[i]);
for(int j=start;j<m;j+=primes[i])
    flags[j]=false;

此外，我对您的筛子做了一些小改动以加快速度。我没有检查素数模数后的每个数字，而是从 prime^2 开始(其中 ^ 表示求幂)并递增 prime，只标记倍数，没有浪费支票。

原创

primes[counter]=i;
counter=counter+1;
for(int j=i+1;j<=(int)Math.sqrt(m);j++)
{
    if(j%i==0)
    {
        v[j]=false;
    }
}

优化

primes[counter++]=i;
for(int j=i*i;j<=(int)Math.sqrt(m);j+=i)
{
    v[j]=false;
}

放在一起-

import java.util.Scanner;
import java.util.Arrays;
public class SegmentedSieveofEratosthenes  {

    public static void main(String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int m = in.nextInt();
        boolean[] v = new boolean[1000000];
        int[] primes = new int[1000000];
        //counter for the primes vector
        int counter = 0;

        for(int i=2;i<=(int)Math.sqrt(m);i++)
        {
            v[i]=true;
        }

        for(int i=2;i<=(int)Math.sqrt(m);i++)
        {
            if(v[i])
            {
                primes[counter++]=i;
                for(int j=i*i;j<=(int)Math.sqrt(m);j+=i)
                {
                    v[j]=false;
                }
            }
        }

        boolean[] flags = new boolean[1000000];
        for(int i=n;i<m;i++)
        {
            flags[i]=true;
        }

        for(int i=0;i<counter;i++)
        {
            int start = n + (-n % primes[i]);
            for(int j=start;j<m;j+=primes[i])
                if (j != primes[i])
                    flags[j]=false;
        }

        for(int i=n;i<m;i++)
            if(flags[i])
                System.out.println(i);

        in.close();
    }
}

例如 n = 800 和 m == 1000 的输出

809
811
821
823
827
829
839
853
857
859
863
877
881
883
887
907
911
919
929
937
941
947
953
967
971
977
983
991
997