6

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

这是我的主要方法:

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

9 回答 9

5

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

您似乎主要关心 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);
于 2013-01-07T16:54:46.610 回答
3
  1. 您可以通过将已经找到的素数存储在PrimeGenerator. 通过仅尝试将它们作为潜在除数而不是for(int i = 2; i < number; i++)循环,您将不得不做更少的除数
  2. 您可以在到达number: 之前停止“查找除数”循环,具体来说,当您的候选除数超过目标数的平方根时,您可以停止。这是可行的,因为您按升序尝试候选除数:如果平方根上方有除数,则除法的结果将低于平方根,因此您已经找到了它们。
  3. 在将值返回给调用者之前,您的getNextPrime方法应该在内部调用。isPrime否则,调用getNextPrime不能说返回下一个素数。
于 2013-01-02T13:35:10.270 回答
3

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

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

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

for(int i = 2; i < (number/2); i++)
于 2013-01-02T14:13:15.643 回答
2

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

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

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;
 }
于 2013-01-02T13:33:13.820 回答
2

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

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. ;)
    }
}
于 2013-01-02T13:35:44.850 回答
1

为什么会PrimeGenerator产生不是素数的数字?这不优雅。删除isPrime()- 方法并重写getNextPrime()- 方法,使其始终返回质数。

于 2013-01-02T14:06:04.497 回答
1

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

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

所以我的观点如下。如果我们想找到最大 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;
    }
}
于 2013-01-02T14:06:15.790 回答
1

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

 **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");
         }
    }**
于 2013-12-05T15:16:38.027 回答
0

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

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;
    }
于 2014-12-10T18:34:44.473 回答