还有没有比这种方法更有效，更简洁的求素数的方式了？代码可以正常工作，但是我只是写了对我来说最合理的东西，我找不到其他方法，但是说实话，它看起来并不好: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);
        }
    }
}

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/