虽然这个问题已经得到回答,但我想我还是会提供我的答案,希望有人会觉得它有用:
您似乎主要关心 2 优雅和效率。我还想指出,正确性同样重要。除非您有特殊要求将数字 1 视为素数,否则不再考虑。您应该同样考虑用户输入质数时的情况。您还应该考虑打印的数字的边界条件。具体来说,如果我输入数字 7,您的用户会期望它输出 5、3、2、1 还是 7、5、3、2、1。虽然我个人倾向于后者,但使用清晰简洁的信息可以使任何一个选项都起作用。
优雅
在您的解决方案中感觉缺乏优雅主要是由于您结合了两个概念:质数测试和质数生成。
素数测试是一种(快速)方法,用于确定单个任意选择的数字是否为素数。素数生成器是一种生成通常是连续的素数序列的方法。
正如您的程序演示的那样,您可以通过测试给定范围内的每个数字并仅选择那些素数来生成连续的素数序列!暂时将此作为我们的基本策略,让我们弄清楚代码可能是什么:
根据我们之前的描述,我们说质数测试是一种方法(又名函数),用于确定某个任意选择的数字是否为质数。所以这个方法应该把一个(n个任意选择的)数字作为输入,并返回给定的数字是否是素数(即:真/假)。让我们看看它的外观:
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);
}
}
效率
现在,您问题的另一面是确定指定范围内的素数的有效方法。虽然快速的互联网搜索应该产生许多不同的“快速”算法来确定一组比蛮力方法快得多的素数。一种这样的方法是阿特金筛法:
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();
}
}
我们现在可以方便地使用这个素数生成器,只需在我们之前的主程序中更改一行!
改变:
//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);