如何创建最紧凑的映射n→isprime(n)直到极限N? [英] How to create the most compact mapping n → isprime(n) up to a limit N?

问题描述

自然地，对于bool isprime(number)，会有一个我可以查询的数据结构.
我定义最佳算法，使其成为在(1，N)范围内具有最低内存消耗的数据结构，其中N是一个常数.
只是我要寻找的一个示例:我可以用一位来表示每个奇数，例如对于给定的数字范围(1，10)，从3开始:1110

Naturally, for bool isprime(number) there would be a data structure I could query.
I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a constant.
Just an example of what I am looking for: I could represent every odd number with one bit e.g. for the given range of numbers (1, 10], starts at 3: 1110

以下字典可以被更多压缩，对吗?我可以通过一些工作消除5的倍数，但是以1、3、7或9结尾的数字必须存在于位数组中.

The following dictionary can be squeezed more, right? I could eliminate multiples of five with some work, but numbers that end with 1, 3, 7 or 9 must be there in the array of bits.

我该如何解决问题?

推荐答案

有许多方法可以执行 primality测试.

实际上没有供您查询的数据结构.如果您要测试的数字很多，则应该运行概率测试，因为更快，然后进行确定性测试，以确保该数字是素数.

There isn't really a data structure for you to query. If you have lots of numbers to test, you should probably run a probabilistic test since those are faster, and then follow it up with a deterministic test to make sure the number is prime.

您应该知道，最快的算法背后的数学运算并不适合胆小的人.

You should know that the math behind the fastest algorithms is not for the faint of heart.

这篇关于如何创建最紧凑的映射n→isprime(n)直到极限N?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！