-4

考虑以下问题：“在给定的整数范围内，有多少个数字的数字和和平方和都是质数？”

我正在查看codereview，在这里我发现了一个有趣的问题并试图解决它。

因此可以prime numbers以一种普通的方式进行检查，即使用for循环 from 2toi并检查可分性。

有趣的事情就在这里。BlueRaja - Danny Pflughoeft建议一个技巧：“由于您只需要筛选到要测试素数的数字的平方根，因此您只需要将筛选器从 3 运行到* sqrt(⌈log10(B)⌉*81)”。

我有一个关于实施的问题Sieve of Eratosthenes。
的大小是多少boolean array，其中包含要处理筛子的数字。？有人可以写代码或任何提示吗？

4

1 回答 1

1

下面是使用 Java 实现埃拉托色尼筛法的示例：链接。

对于您的问题的第二部分，请参阅此链接：

"一个n位数的最大平方和是n*9*9 = n*81。一个数B的位数是⌈log10(B)⌉。既然你只需要筛分到您要测试素数的数字的平方根，您只需要将筛子从 3 运行到 sqrt(⌈log10(B)⌉*81)。即使 B = 10 亿，这意味着您需要筛分的最大值到 28 岁。”

于 2012-04-15T18:48:58.860 回答