还有没有比这种方法更有效，更简洁的求素数的方式了？代码可以正常工作，但是我只是写了对我来说最合理的东西，我找不到其他方法，但是说实话，它看起来并不好:P。我知道编码并不是最优雅的 Activity 。
这是我的主要方法:import java.util.Scanner;
public class DisplayPrimeNumbers
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.print("Enter an integer that you'd like the system to print the prime numbers till: ");
String input1 = scan.nextLine();
int input = Integer.parseInt(input1);
PrimeGenerator prime = new PrimeGenerator(input);
for (int i = 1; i < input ; i++)
{
if(prime.isPrime())
{
System.out.println(prime.getNextPrime());
}
}
System.out.println(1);
}
}
这是我的课:public class PrimeGenerator
{
private int number;
public PrimeGenerator(int n)
{
number = n;
}
public int getNextPrime ()
{
return number+1;
}
public boolean isPrime()
{
for(int i = 2; i < number; i++)
{
if (number % i == 0)
{
number--;
return false;
}
}
number--;
return true;
}
}
最佳答案
虽然已经回答了这个问题，但我还是想提供答案，希望有人会发现它有用:
您似乎主要关注2的优雅和效率。我还要指出，正确性同样重要。除非您有特殊要求将数字1视为质数，否则不再考虑。您同样应该考虑用户输入素数时的情况。您还应该考虑打印什么数字的边界条件。具体来说，如果我输入数字7，您的用户会期望它输出5、3、2、1或7、5、3、2、1。虽然我个人倾向于使用后者，但是使用简洁明了的消息可以使这两种选择都起作用。
优雅
解决方案中缺乏优雅感的主要原因是两个概念的组合:素数测试和素数生成。
质数测试是一种(快速)方法，用于确定一个任意选择的数字是否为质数。
质数生成器是一种生成通常是连续的质数序列的方法。
如您的程序所示，可以通过测试给定范围内的每个数字并仅选择那些质数来生成连续的质数序列!暂时将其作为我们的基本策略，让我们弄清楚代码可能是什么:
根据前面的描述，我们说质数测试是一种确定某些任意选择的数是否为质数的方法(又称函数)。因此，此方法应将(任意选择的)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);
}
}
}
但是，您的主程序应仅关注素数生成。它实际上并不关心那些素数如何生成的语义，我们只需要素数。是否通过素数测试或任何其他算法找到素数并不重要。因此，我们问自己一个素数生成器是什么样的？
对于初学者来说，素数始终是整数，因此我们不应该将它们存储在浮点数， double 数或十进制数内。剩下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);
关于java - 还有什么比这更容易找到质数的方法呢？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14122977/