この質問はすでに回答されていますが、誰かが役立つことを期待して、とにかく回答を提供すると思いました。
あなたは主にエレガンスと効率の両方に関心があるようです。また、正確性も同様に重要であることを指摘したいと思います。数値 1 を素数として扱う特別な要件がない限り、素数とは見なされなくなりました。ユーザーが素数を入力する場合のシナリオも同様に考慮する必要があります。また、出力する数値の境界条件についても考慮する必要があります。具体的には、数字の 7 を入力した場合、ユーザーはそれが 5,3,2,1 または 7,5,3,2,1 を出力することを期待しますか? 私の個人的な傾向は後者ですが、明確で簡潔なメッセージを使用すると、どちらのオプションも機能します。
優雅
ソリューションにエレガンスが欠けていると認識されているのは、主に素数テストと素数生成という 2 つの概念の組み合わせによるものです。
素数テストは、任意に選択された単一の数が素数であるかどうかを判断する (迅速な) メソッドです。素数ジェネレーターは、多くの場合連続する一連の素数を生成する方法です。
プログラムが示すように、指定された範囲内の各数値をテストし、素数である数値のみを選択することで、素数の連続したシーケンスを生成できます。これを当面の基本的な戦略として維持し、コードがどのようなものになるかを考えてみましょう:
前の説明から、素数テストは、任意に選択された数が素数であるかどうかを判断するためのメソッド (別名関数) であると述べました。したがって、このメソッドは入力として (n 任意に選択された) 数値を取り、指定された数値が素数であるかどうか (つまり、true/false) を返す必要があります。それがどのように見えるか見てみましょう：
public interface PrimeNumberTest
{
bool isPrime(int value);
}
素数テストを組み込む
public class BruteForcePrimeNumberTester : PrimeNumberTest
{
public bool isPrime(int value)
{
bool isPrime = true;
for(int i = 2; isPrime && i < value; i++)
{
if (value % i == 0)
{
isPrime = false;
}
}
return isPrime;
}
}
次に、メイン プログラムは、各数値を繰り返し処理し、素数テストで素数と識別されたものだけを出力します。
public static void main(String[] args)
{
//Determine the range of prime numbers to print
Scanner scan = new Scanner(System.in);
System.out.print("Primes smaller than what number should be printed?: ");
int max = Integer.parseInt(scan.nextLine());
//Identify how prime numbers will be tested
PrimeNumberTest test = new BruteForcePrimeNumberTest();
//Uncomment the line below if you want to include the number 1. Favour adding it here so that you may
//use re-use your prime number test elsewhere that atually needs to know if a number is prime.
//System.out.println(1);
//Print the prime numbers
for (int i = 2; i < max ; i++)
{
if(test.isPrime(i))
{
System.out.println(i);
}
}
}
ただし、メイン プログラムは、素数の生成のみに関係する必要があります。これらの素数がどのように生成されるかというセマンティクスはあまり気にしません。素数が必要なだけです。素数が素数性テストまたは他のアルゴリズムによって見つかったかどうかは問題ではありません。それでは、素数ジェネレーターはどのように見えるのでしょうか?
まず、素数は常に整数であるため、浮動小数点数、倍精度浮動小数点数、または小数の中に格納しないでください。これにより、32 ビットと 64 ビットの整数が残ります。より大きな素数を生成したい場合は、明らかにlong型を使用する必要がありますが、ここでは を使用しますint。他の言語では、符号なしの数値なども考慮する必要があります。
次に、これらすべての数値を一度に返す方法を見つける必要があります。連続したシーケンスを生成するので、ツリーはあまり意味がありません。消費者は通常、生成された順序で数値を求めているため、スタックは意味がありません。先入れ先出しの規則に適合するため、キューを使用できます。実際、エンド アプリケーションに非同期素数ジェネレーター (プロデューサー) と別の非同期コンシューマーがある場合、このタイプが理想的です。ただし、この例では、読み取り専用が必要です。基本的に、素数ジェネレータはIterable<int>.
public class PrimeNumberTestGenerator : Iterable<int>
{
private int limit;
private PrimalityTester tester;
public PrimeNumberTestGenerator(PrimalityTester tester, int limit)
{
this.tester = tester;
this.limit = limit;
}
private class PrimeNumberIterator : Iterator<int>
{
private int current;
public PrimeNumberIterator()
{
}
public bool hasNext()
{
return next < limit;
}
public int moveNext()
{
if (!hasNext())
{
throw new NoSuchElementException();
}
int result = next;
do
{
next++;
} while(hasNext() && !tester.isPrime(next));
return result;
}
public void remove()
{
throw new UnsupportedOperationExecution();
}
}
public Iterator<int> iterator()
{
return new PrimeNumberIterator();
}
}
では、それらをどのように結びつけるのでしょうか。
public static void main(String[] args)
{
//Determine the range of prime numbers to print
Scanner scan = new Scanner(System.in);
System.out.print("Primes smaller than what number should be printed?: ");
int max = Integer.parseInt(scan.nextLine());
//Identify how prime numbers will be tested
Iterable<int> primes = new PrimeNumberTestGenerator(max, new BruteForcePrimeNumberTest());
//Print the prime numbers
foreach (int prime : primes)
{
System.out.println(prime);
}
}
効率
あなたの質問の反対側は、指定された範囲内で素数を決定する効率的な方法でした。簡単なインターネット検索では、力ずくの方法よりもはるかに高速な一連の素数を決定するためのさまざまな「高速」アルゴリズムが得られるはずです。そのようなアプローチの 1 つが Atkin のふるいです。
public class AtkinSieve : Iterable<int>
{
private BitSet primes;
public AtkinSieve(int limit)
{
primes = new BitSet(limit);
int root = (int)Math.sqrt(limit);
primes.set(2);
primes.set(3);
//this section can be further optimized but is the approach used by most samples
for (int x = 1; x <= root; x++)
{
for (int y = 1; y <= root; y++)
{
int number;
int remainder;
number = (4 * x * x) + (y * y);
remainder = number % 12;
if (number < limit && (remainder == 1 || remainder == 5))
{
primes.flip(number);
}
number = (3 * x * x) + (y * y);
remainder = number % 12;
if (number < limit && remainder == 7)
{
primes.flip(number);
}
if (x < y)
{
number = (3 * x * x) - (y * y);
remainder = number % 12;
if (number < limit && remainder == 11)
{
primes.flip(number);
}
}
}
}
for (int i = 5; i <= root; i++)
{
if (primes.get(i))
{
int square = i * i;
for (int j = square; j < limit; j += square)
{
primes.clear(j);
}
}
}
}
}
public class SetBitIterator : Iterator<int>
{
private BitSet bits;
private int next;
private bool isReadOnly;
public SetBitIterator(BitSet bits)
{
this.bits = bits;
next = bits.nextSetBit(0);
}
public bool hasNext()
{
return next <> -1;
}
public int moveNext()
{
int result = next;
next = bits.nextSetBit(next);
return result;
}
public void remove()
{
throw new UnsupportedOperationException();
}
}
便利なことに、以前のメイン プログラムの 1 行を変更するだけで、この素数ジェネレータを使用できるようになりました。
変化する：
//Identify how prime numbers will be tested
Iterable<int> primes = new PrimeNumberTestGenerator(max, new BruteForcePrimeNumberTest());
に：
//Identify how prime numbers will be tested
Iterable<int> primes = new AtkinSieve(max);