1

私たちは、エラトステネスのふるいアルゴリズムに対応する 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

あなたのアルゴリズムはエラトステネスのふるいではありません。これは、試行除算の実装が不十分です (モジュロ演算子がそれを提供します)。私のエッセイ 素数によるプログラミング では、エラトステネスのふるいアルゴリズムについて詳しく説明し、あなたが犯した非常に一般的なエラーについて説明し、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 に答える