1

我们被指派制作一个与 Eratosthenes 算法的 Sieve 并行的 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));              
}

}
4

1 回答 1

0

你的算法不是埃拉托色尼筛法；这是试验除法的糟糕实现（模运算符放弃了它）。我的文章 Programming with Prime Numbers详细描述了 Sieve of Eratosthenes 算法，讨论了您犯的非常常见的错误，并在 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;
}
于 2012-10-30T12:49:35.023 回答