当前位置: 首页 > 知识库问答 >
问题:

在素数范围内查找最大出现位数

司马钱明
2023-03-14

给定两个数a和b(1<=a<=b<=10^6)。在a和b之间的所有素数中找出最常见的数字。如果频率相同,则打印最高数字。

例:从1到20,素数是-2,3,5,7,11,13,17,19。这里2,5,9只出现一次,3,7出现两次,1出现5次。所以结果是1。

一个基本方法是:

  • 在[a,b]范围内-求所有素数。
  • 取一个数组计算0到9之间的出现次数。
  • 对于范围内的所有素数,提取所有数字,并相应地增加计数数组中数字的计数。
  • 从计数数组中找出最大值。

但对于较大的范围(例如[1,1000000])而言,这是低效的。

有没有什么有效的方法来完成这一点?

共有1个答案

朱丰
2023-03-14

做一个Eratosthenes的筛子,找出0,106范围内的所有素数。这可以非常快地完成(在一台普通的机器上不到1秒)。使用10个辅助数组--每个数字一个,每个数组大小为106。如果一个数不是素数,则将所有10个数组存储为0。如果一个数字是素数,则在每个数组中存储给定数字在该数字中出现的次数。然后在每一个数组上循环,并累加给定数字的出现次数的前缀和。这可以在线性时间内相当容易地完成。对数字3说:

for (int i = 1; i < n; ++i) {
   a3[i] += a3[i-1];
}

有了这些数组,您就可以在恒定时间内计算指定时间间隔内每个数字出现的次数。即[x,y]区间中3的出现次数为A3[y]-A3[x-1](当x为0时要注意特殊情况)。

该算法的计算复杂度与Eratosthenes的Sileve算法的计算复杂度相同,对每个查询的计算复杂度为常数。存储器复杂度是线性的。您可以通过在辅助数组中仅存储素数的值来提高内存开销,从而使它们的大小等于素数的个数,如果需要,最多可以达到106。然而,这会使实现略显棘手。

 类似资料:
  • 问题内容: 我有以下三个简单的T-SQL查询。第一个是获取一定范围内的记录(DATETIME类型): 第二个是获取最接近@startDT的记录(DATETIME类型) 最后一个是获取@endDT之后最接近的记录: 我想将以上三个查询的所有记录作为一组记录。我尝试使用UNION,但似乎UNION中的子查询不允许使用ORDER BY子句。有没有有效的方法来得到我的结果? 上图仅将* s的记录显示为我的

  • Python3 实例 素数(prime number)又称质数,有无限个。除了1和它本身以外不再被其他的除数整除。 以下实例可以输出指定范围内的素数: 实例(Python 3.0+)#!/usr/bin/python3 # 输出指定范围内的素数 # take input from the user lower = int(input("输入区间最小值: ")) upper = int(input(

  • 我无法降低这个问题的复杂性。请给出一些更好的方法。 有没有一个我不知道的数学公式,或者它可以用更好的方法来完成? 我是这样做的:

  • 我想知道是否有一个java函数可以检查索引0-5中的值?例如在不使用循环的情况下,有一个函数将子数组1[0-5]中的元素标识为{1,2,3,4,5}

  • 所以我必须写一个程序,找到给定范围之间的所有回文数。程序必须使用numDigits()方法,该方法接受int数并返回该int的位数。 一个isPalindrome()方法,它将接受一个int数字,并返回一个布尔值true或false,无论该数字是否回文 我在这里编码了一个numDigit()方法: 我知道如何用另一种方法找到回文,但作业是专门针对这种技术的。我如何实现这个numDigit()方法来

  • 因此,我必须编写一个程序,使用numDigits方法找到一个范围内的所有回文数,该方法取一个int数并返回该数的位数,使用isPalindrome方法取一个int数并返回一个布尔值true或false。这是在爪哇。 我有一个numDigits方法编码,工作很好,但我不知道如何获得它的输出,并使用它找到一个范围内的所有回文 null