检查int是否更有效率 [英] Checking if an int is prime more efficiently

问题描述

我最近参加了我校的一个小型java编程比赛。我的伙伴和我刚刚完成了我们的第一个纯oop课程，大部分问题都在我们的联盟之外，所以我们确定了这个问题（我在某种程度上解释）：给定一个输入整数n，返回下一个整数和它的反向也是素数，例如，如果n = 18，你的程序应该打印31因为31和13都是素数。然后，您的.class文件将包含一个测试用例，其中包含1-2,000,000,000个传递给它的所有可能数字，并且必须在10秒内返回正确答案才能被视为有效。

I recently was part of a small java programming competition at my school. My partner and I have just finished our first pure oop class and most of the questions were out of our league so we settled on this one (and I am paraphrasing somewhat): "given an input integer n return the next int that is prime and its reverse is also prime for example if n = 18 your program should print 31" because 31 and 13 are both prime. Your .class file would then have a test case of all the possible numbers from 1-2,000,000,000 passed to it and it had to return the correct answer within 10 seconds to be considered valid.

我们找到了一个解决方案，但测试用例较大，需要的时间超过10秒。我相当确定有一种方法可以将n，... 2,000,000,000的循环范围向下移动，因为当n是一个较小的数字时，需要循环的可能性很小，但是无论哪种方式我们在一个数字时打破了循环在这两种情况下都是素数。起初我们从2，... n循环，无论它有多大，我都记得关于只循环到n的平方根的规则。有关如何提高程序效率的任何建议？我没有处理算法复杂性分析的课程。这是我们的尝试。

We found a solution but with larger test cases it would take longer than 10 seconds. I am fairly certain there is a way to move the range of looping from n,..2,000,000,000 down as the likely hood of needing to loop that far when n is a low number is small, but either way we broke the loop when a number is prime under both conditions is found. At first we were looping from 2,..n no matter how large it was then i remembered the rule about only looping to the square root of n. Any suggestions on how to make my program more efficient? I have had no classes dealing with complexity analysis of algorithms. Here is our attempt.

public class P3
{

   public static void main(String[] args){

    long loop = 2000000000;
    long n = Integer.parseInt(args[0]);
    for(long i = n; i<loop; i++)
    {
      String s = i +"";
      String r = "";
      for(int j = s.length()-1; j>=0; j--)
        r = r + s.charAt(j);
      if(prime(i) && prime(Long.parseLong(r)))
      {
          System.out.println(i);
          break;
      }
    }
    System.out.println("#");
  }

  public static boolean prime(long p){


for(int i = 2; i<(int)Math.sqrt(p); i++)
    {
      if(p%i==0)
        return false;
    }
    return true;
  }
}

抱歉，如果我对代码格式化错了这个是我第一次在这里发帖。此外，输出必须在每一行之后有一个'＃'表示循环之后的行是什么感谢你们提供的任何帮助!!!

ps sorry if i did the formatting for code wrong this is my first time posting here. Also the output had to have a '#' after each line thats what the line after the loop is about Thanks for any help you guys offer!!!

推荐答案

首先，你应该使用像 Eratosthenes筛选。你可以存储每个数字是否是位数组中的素数。

First you should precompute all prime numbers up to 2,000,000,000 using something like the Sieve of Eratosthenes. You can store whether each number is prime in a bit array.

这非常快，然后检查每个单独的数字是否为素性是一个简单的查找。

This is pretty fast, and then checking each individual number for primality is a simple lookup.

如果由于需要为每个测试用例运行程序的新实例而无法执行此操作，请使用快速素数测试算法，如 Miller-Rabin 。

If you can't do this because you need to run a new instance of your program for each test case, use a fast primality testing algorithm like Miller-Rabin.

这篇关于检查int是否更有效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！