algorithm - 需要使用数组在 Java 中使程序与埃拉托色尼筛法并行

Question

我们被指派编写一个 Java 程序，该程序与埃拉托色尼筛分算法并行。我以我所知道的每一种方式都尝试了好几次，但一直没能成功。我应该使用质数小于估算数的填充数组。这是我的代码，有人可以帮我仔细检查程序和/或弄清楚为什么我会收到这个错误吗？任何帮助表示赞赏。

import java.text.DecimalFormat;
import java.util.Scanner;

import java.util.Arrays;



public class Lab6st
{
static int MAX = 100;
static int i;
static int k;
static int intArray;
static int isPrime;

public static void main(String args[]) 
{
    System.out.println("\nLAB12 100 Point Version");
    Scanner input = new Scanner(System.in);
    boolean primes[] = new boolean[MAX];
    computePrimes(primes);
    displayPrimes(primes);
    Arrays.fill(primes,true);
}

public static void computePrimes(boolean primes[])
{
    System.out.println("\nCOMPUTING PRIME NUMBERS");
    for (int i = 1; i < MAX; i++);
    {
        for (i=1; i < MAX; i++ );
        for (k=2; k<i; k++){
            int n = i%k;
            if (n==0)
            {
                break;
            }
        }
        if (i==k);
        {
            primes[i] = true;
        }       
    }
}

public static void displayPrimes(boolean primes[])
{
    System.out.println("\n\nPRIMES BETWEEN 1 AND "+ primes.length);
    for (int isPrime = 0; isPrime < MAX; isPrime++);
        if (primes[isPrime] == true);
            System.out.println(Arrays.asList(primes));              
}

}

Answer 1

您的算法不是埃拉托色尼筛法；这是试用除法的糟糕实现(模运算符将其泄露)。我的essay Programming with Prime Numbers 详细描述了埃拉托色尼筛法算法，讨论了您所犯的非常常见的错误，并在 Java 中包含了此实现:

public static LinkedList sieve(int n)
{
    BitSet b = new BitSet(n);
    LinkedList ps = new LinkedList();

    b.set(0,n);

    for (int p=2; p<n; p++)
    {
        if (b.get(p))
        {
            ps.add(p);
            for (int i=p+p; i<n; i+=p)
            {
                b.clear(i);
            }
        }
    }

    return ps;
}