检查一个 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 抱歉，如果我的代码格式错误，这是我第一次在这里发帖.此外，输出必须在每一行之后有一个#"，这就是循环之后的行的含义 感谢你们提供的任何帮助！！！

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!!!

推荐答案

首先，您应该使用 埃拉托色尼筛法.您可以将每个数字是否为素数存储在位数组中.

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屋！