java - 如何生成特殊数字？

Question

我需要生成前 20 个素数，以 1 开头，第二个数字是 3。 我知道如何检查一个数字是否是质数，但我在其他部分发现了困难。

有人可以给我更多关于生成一些具有特殊特征的数字的练习吗，因为我发现它们有困难。谢谢

  public static int isprime(int x){
         for(int i=2;i<x;i++)
               if(x%i==0)
                  return false;
        return true;  }

Answer 1

首先，您的 isPrime() 方法可能会更高效一些。检查超出数字平方根的因子是没有意义的，因为如果它们存在，您就会发现它们的伙伴已经低于平方根。因此，您可以将 for 语句的继续条件设置为如下所示:

for (int i = 2; i * i <= x; i++)

您还可以通过仅检查 2 之后的奇数来将速度大致提高一倍。

假设它们不会太大，您可以将它们转换为字符串并查看它是否以 "13" 开头。

在 Java 中，Long.toString() 和 String.startsWith() 可能是完成这项工作的最佳工具。

如果您想自己解决这个问题，那么现在就去做，因为我在下面提供了完整的解决方案。

<小时/>

还在吗？我假设您已经尝试过，或者您只是想要一个解决方案。

例如，参见以下程序:

public class Test {
    public static boolean isPrime (long num) {
        if ((num % 2) == 0) {
            return false;
        }
        for (long chk = 3; chk * chk <= num; chk += 2) {
            if ((num % chk) == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        for (long num = 2, count = 0; count < 20; num++) {
            if (Long.toString(num).startsWith("13")) {
                if (isPrime(num)) {
                    count++;
                    System.out.println ("#" + count + ": " + num);
                }
            }
        }
    }
}

生成:

#1: 13
#2: 131
#3: 137
#4: 139
#5: 1301
#6: 1303
#7: 1307
#8: 1319
#9: 1321
#10: 1327
#11: 1361
#12: 1367
#13: 1373
#14: 1381
#15: 1399
#16: 13001
#17: 13003
#18: 13007
#19: 13009
#20: 13033

<小时/>

如果您需要大量数据(例如前 200 万而不是前 20 个)，最后的一点优化可能会提高性能。

为此，我们从 13 开始，然后，只要您的号码以 14 开头，您就可以跳过一大块候选者(例如 14到 129(含)，或从 140,000 到 1,299,999(含)。

这可确保您只检查以 13 开头的数字，例如 13、130-139、 1,300-1,399、13,000-13,999 等等。您还可以通过仅检查奇数来加快速度。使用部分数字检查还意味着我们不需要进行字符串转换，我们恢复到纯数字操作，这可能是有益的。

为此，请对代码进行以下更改:

public class Test {
    public static boolean isPrime (long num) {
        if ((num % 2) == 0) {
            return false;
        }
        for (long chk = 3; chk * chk <= num; chk += 2) {
            if ((num % chk) == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        for (long num = 13, end = 14, count = 0; count < 2000000; num += 2) {
            // Code to move from 140..0 to 1299..9

            if (num >= end) {
                end = end * 10;
                num = (end / 14) * 13 - 1;
                continue;
            }
            if (isPrime(num)) {
                count++;
                System.out.println ("#" + count + ": " + num);
            }
        }
    }
}

这将前 200 万个数字的运行时间从 394 秒减少到 323 秒，下降了 18%。