java 还有比这更简单的求素数的方法吗？

Any easier way of finding prime numbers than this?

提问by Waj

is there a more efficient, cleaner/elegantway of finding prime numbers than this? The code works fine, but I just wrote what seemed most logical to me and I can't figure out any other way, but to be honest it just doesn't look nice :P. I know coding isn't the most elegant of activities.

有没有比这更有效、更清洁/更优雅的查找素数的方法？代码工作正常，但我只是写了对我来说最合乎逻辑的东西，我想不出任何其他方式，但说实话，它看起来不太好：P。我知道编码不是最优雅的活动。

Here's my main method:

这是我的主要方法：

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);

    }
}

Here's my class:

这是我的课：

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;    
    }
} 

采纳答案by Chris Kerekes

While this question has already been answered I figured I'd provide my answer anyway in the hopes that somebody may find it useful:

虽然这个问题已经得到回答，但我想我还是会提供我的答案，希望有人会觉得它有用：

You seem to be primarily concerned with 2 both elegance and efficiency. I'd also like to point out that correctness is equally important. Unless you have a special requirement to treat the number 1 as prime it is no longer considered so. You should equally consider the scenario when the user enters a prime number. You should also give some thought into the boundry condition of what numbers you print. Specifically if I enter the number 7, will your users expect it to output 5,3,2,1 or 7,5,3,2,1. While my personal tendency would be towards the latter, using clear and concise messages can make either option work.

您似乎主要关注 2 优雅和效率。我还想指出正确性同样重要。除非您有特殊要求将数字 1 视为素数，否则不再将其视为素数。您应该同样考虑用户输入质数时的场景。您还应该考虑一下您打印的数字的边界条件。具体来说，如果我输入数字 7，您的用户会希望它输出 5、3、2、1 还是 7、5、3、2、1。虽然我个人倾向于后者，但使用清晰简洁的信息可以使任何一种选择都有效。

Elegance

优雅

The perceived lack of elegance in your solution is largely due to your combination of two concepts: Prime Number Testingand Prime Number Generation.

您的解决方案缺乏优雅的感觉主要是由于您结合了两个概念：质数测试和质数生成。

A Prime Number Testis a (quick) method to determine whether or not a single arbitrarily chosen number is prime. A Prime Number Generatoris a way of generating a sequence of prime numbers which are often consecutive.

质数测试是一种（快速）方法，用于确定单个任意选择的数字是否为质数。素数生成器是一种生成素数序列的方法，这些素数通常是连续的。

As your program demonstrates you can generate a consecutive sequence of prime numbers by testing each number within a given range and only selecting those which are prime! Keeping this as our basic strategy for the moment, let's figure out what the code might:

正如您的程序所展示的，您可以通过测试给定范围内的每个数字并仅选择那些质数来生成连续的质数序列！暂时将此作为我们的基本策略，让我们弄清楚代码可能会做什么：

From our description earlier we said that a prime number test was a method (aka function) to determine if some arbitrarily chosen number was prime. So this method should take as input a(n arbitrarily chosen) number and return wether or not the given numbe was prime (ie: true/false). Let's see how it looks:

从我们之前的描述中，我们说过素数测试是一种确定某个任意选择的数字是否为素数的方法（又名函数）。因此，此方法应将一个（n 任意选择的）数字作为输入，并返回给定的数字是否为素数（即：真/假）。让我们看看它的外观：

public interface PrimeNumberTest
{
    bool isPrime(int value);
}

And incorporating your prime number test

并结合您的质数测试

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;
    }
}

Your main program is then responsible for iterating over each number and printing only thsoe which the prime number test identifies as prime.

然后，您的主程序负责迭代每个数字并仅打印质数测试识别为质数的那些。

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);
        }
    }
}

Your main program however should only be concerned with prime number generation. It doesn't really care about the semantics of howthose primes are generated we just want the primes. It doesn't really matter if the primes were found via primality testing or any other algorithm. So we ask ourselves what does a prime number generator look like?

但是，您的主程序应该只关注素数生成。它并不真正关心如何生成这些素数的语义，我们只需要素数。如果通过素性测试或任何其他算法找到素数并不重要。所以我们问自己素数生成器是什么样子的？

For starter primes are always whole numbers so we shouldn't be storing them inside floats, doubles or decimals. That leaves 32 and 64 bit integers. If you want to generate larger prime numbers then obviously you should use the longtype but I'm just going to use int. In other languages we would also have to consider things like unsigned numbers too.

首先，素数总是整数，所以我们不应该将它们存储在浮点数、双精度数或小数中。这留下了 32 位和 64 位整数。如果你想生成更大的素数，那么显然你应该使用long类型，但我只会使用int. 在其他语言中，我们也必须考虑诸如无符号数之类的东西。

Now we need to find a way to return all of these numbers at once. Trees don't really make sense as we're going to be generating a consecutive sequence. Stacks don't make sense because consumers typically want the numbers in the order they were generated. Queues could be used as they fit the first-in-first-out rule. In fact if the end application had an asynchronous prime number generator (producer) and a separate asynchronous consumer this type would be ideal. For this example however I want something read-only. Essentially a prime number generator is an Iterable<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();
    }
}

So how do we tie them together?

那么我们如何将它们联系在一起呢？

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);
    }
}

Efficiency

效率

Now the other side of your question was an efficient way of determining the prime numbers within a specified range. While a quick internet search should yield a number of different "fast" algorithms for determing a set of prime numbers that are much faste than the brute force way. One such approach is the Sieve of 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();
    }
}

Conveniently we can now use this prime number generator by only changing a single line in our previous main program!

方便地，我们现在可以通过只更改我们以前的主程序中的一行来使用这个素数生成器！

Change:

改变：

//Identify how prime numbers will be tested
Iterable<int> primes = new PrimeNumberTestGenerator(max, new BruteForcePrimeNumberTest());

To:

到：

//Identify how prime numbers will be tested
Iterable<int> primes = new AtkinSieve(max);

回答by dasblinkenlight

1. You can speed up your search for new primes by storing the primes that you have already found in a private collection inside the PrimeGenerator. By trying only them as potential divisors instead of your for(int i = 2; i < number; i++)loop, you will have to do much fewer divisions
2. You can stop the "find divisors" loop well before you reach the number: specifically, you can stop when your candidate divisor exceeds the square root of the target number. This works, because you try the candidate divisors in ascending order: if there were divisors above the square root, the result of the division would have been below the square root, so you would have already found them.
3. Your getNextPrimemethod should call isPrimeinternally before returning the value to the caller. Otherwise, the call of getNextPrimecannot be said to return the next prime.

1. 您可以通过将已在私人集合中找到的素数存储在PrimeGenerator. 通过仅尝试将它们作为潜在的除数而不是for(int i = 2; i < number; i++)循环，您将需要进行更少的除法
2. 您可以在到达number:之前很好地停止“查找除数”循环：特别是，当您的候选除数超过目标数的平方根时，您可以停止。这是有效的，因为您按升序尝试候选除数：如果平方根上方有除数，则除法的结果将低于平方根，因此您已经找到了它们。
3. 在将值返回给调用者之前，您的getNextPrime方法应该在isPrime内部调用。否则，getNextPrime不能说的调用返回下一个素数。

回答by Saty

First and most important thing is.... U need not to check till i

首先也是最重要的事情是......你不需要检查，直到我

for(int i = 2; i < number; i++)

U need to to check only untill i is less than number/2...

你只需要检查直到 i 小于 number/2 ...

for(int i = 2; i < (number/2); i++)

回答by Peter Lawrey

This is how I might have written it for simplicity

为了简单起见，我可能是这样写的

public static void main(String... args) {
    System.out.print("Enter an integer that you'd like the system to print the prime numbers till: ");
    Scanner scan = new Scanner(System.in);
    int input = scan.nextInt();

    if (input >= 2)
        System.out.println(2);
    OUTER: for (int i = 3; i <= input; i += 2) { // skip every even number
        for (int j = 3; j * j <= i; j += 2) // stop when j <= sqrt(i)
            if (i % j == 0)
                continue OUTER;
        System.out.println(i); // 99+% of the time will be spent here. ;)
    }
}

回答by SomeJavaGuy

Yeah there are. I don′t know if it′s the most efficient, but it is way more efficient then this one. Check the Miller Rabintest.

是的，有。我不知道它是否是最有效的，但它比这个更有效。检查米勒拉宾测试。

Even so, if you want to work with your Code, i could tell you, you should do it like this:

即便如此，如果你想使用你的代码，我可以告诉你，你应该这样做：

public boolean isPrime(int number)
{
    // You should know, that every straight number can not be prime,so you can say i+= 2
   if (number == 2)
       return true;
   if (number % 2 == 0)
   {
      return false;
   }
    for(int i = 3; i < number; i+=2)
    {
       if (number % i == 0)
       {
          number--;
          return false;
       }
     --number;
     return true;
 }

回答by Razor1692

Try this code mate.I wrote this. This is more elegant i think :)

试试这个代码伙伴。我写了这个。我认为这更优雅:)

 **import java.util.*;

    public class PrimeNum{
    public static void main(String args[]){
           Scanner x=new Scanner(System.in);
           System.out.println("Enter the number :  ");
           long y=x.nextLong();
           long i;
           for( i=2;i<y;i++){
           long z=y%i;
               if(z==0){
               System.out.println(y+" is not a prime");
               System.out.println(y+" Divide by "+i);
               i=y;    
                             }

               }if(i==y) System.out.println("Number is prime"); 
                if(y==1) System.out.println("Number 1 is not a prime");
         }
    }**

回答by COME FROM

Why would a PrimeGeneratorproduce numbers that are not prime? That's not elegant. Remove the isPrime()-method and rewrite the getNextPrime()-method so that it will always return a prime number.

为什么会PrimeGenerator产生不是素数的数字？那不优雅。删除isPrime()-method 并重写getNextPrime()-method 以便它始终返回素数。

回答by Vic

As an improvement you can step by 6 not by 2 and do 2 checks in each step. See what I found here.

作为改进，您可以逐步执行 6 步而不是 2 步，并在每个步骤中进行 2 次检查。看看我在这里找到了什么。

Basically, every number can be written as (6k, 6k + 1, 6k+2, 6k+3, 6k+4, or 6k+5). 6k is clearly not prime. Items 6k+2 to 6k+4 can be written as 2(3k + 1), 3(2k+1), and 2(3k + 2) and therefore aren't prime as they're divisible by 2 or 3.

基本上，每个数字都可以写成 (6k, 6k + 1, 6k+2, 6k+3, 6k+4, or 6k+5)。6k 显然不是素数。项目 6k+2 到 6k+4 可以写成 2(3k + 1)、3(2k+1) 和 2(3k + 2)，因此不是质数，因为它们可以被 2 或 3 整除。

So my point is the following. If we want to find numbers up to 1000 we can do the following thing.

所以我的观点如下。如果我们想找到最多 1000 的数字，我们可以做以下事情。

int [] primes = new int[1000];
primes[0] = 2;
primes[1] = 3;
primes[2] = 5;
primes[3] = 7;
index = 4;
for(int i = 12; i < 1000; i += 6) {
    boolean prime1 = true;
    boolean prime2 = true;
    int j = 1; // No need to divide by 2, the number is odd.
    while(j < index && (prime1 || prime2)) {
        if (prime1 && ((i - 1) % primes[j] == 0)) {
            prime1 = false;
        }
        if (prime2 && ((i + 1) % primes[j] == 0)) {
            prime2 = false;
        }
        j++;
    }
    if (prime1) {
        primes[index++] = i - 1;
    }
    if (prime2) {
        primes[index++] = i + 1;
    }
}

回答by Abhinav

Based on my observations a basic approach would be to use this:

根据我的观察，一个基本的方法是使用这个：

int prime(int up_limit){
        int counter =0;
        for(int i=1;i<=up_limit;i++)
              {
        if(up_limit%i==0)
             counter++;

        }
    if(count==2){
    return up_limit;
    }