java – 找到质数比这更简单的方法吗？

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

虽然这个问题已经得到了回答,但我认为无论如何我都会提供我的答案,希望有人可能会觉得它很有用：

你似乎主要关注优雅和效率.我还想指出正确性同样重要.除非你有特殊要求将1号视为素数,否则不再这样认为.您应该同样考虑用户输入素数时的情况.您还应该考虑一下您打印的数字的边界条件.特别是如果我输入数字7,您的用户是否希望它输出5,3,2,1或7,5,1.虽然我的个人倾向是针对后者,但使用简洁明了的消息可以使任一选项都有效.

优雅

您解决方案中缺乏优雅的主要原因在于您将两个概念组合在一起：素数测试和素数生成.

素数测试是一种(快速)方法,用于确定单个任意选择的数字是否为素数.
素数生成器是一种生成通常连续的素数序列的方法.

正如您的程序演示的那样,您可以通过测试给定范围内的每个数字并仅选择那些素数来生成连续的素数序列！将此作为我们当前的基本策略,让我们弄清楚代码可能是什么：

根据我们之前的描述,我们说素数测试是一种方法(也就是函数)来确定一些任意选择的数字是否为素数.所以这个方法应该作为输入a(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;
    }
}

然后,您的主程序负责迭代每个数字并仅打印素数测试识别为素数的thsoe.

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