为了测试一个数字是否为素数,为什么我们必须测试它是否只能被该数字的平方根整除？
这是我能提出的最佳算法.
def get_primes(n):
numbers = set(range(n, 1, -1))
primes = []
while numbers:
p = numbers.pop()
primes.append(p)
numbers.difference_update(set(range(p*2, n+1, p)))
return primes
>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import get_primes').timeit(1)
1.1499958793645562
可以做得更快吗？
此代码有一个缺陷:由于numbers是无序集,因此无法保证numbers.pop()从集中删除最小数字.然而,它对某些输入数字起作用(至少对我而言):
>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True
作为非密码学家,有一件事总是让我感到震惊:为什么使用Prime数字这么重要？是什么让他们在密码学方面如此特别？
有没有人有简单的简短解释？(我知道有许多引物,应用密码学是圣经,但正如所说的:我不打算实施我自己的加密算法,我发现的东西只是让我的大脑爆炸 - 没有10页的数学公式请 :))
谢谢你的所有答案.我已经接受了让我对这个实际概念最清楚的那个.
我只是想知道为什么在类的hashCode()方法中使用素数？例如,当使用Eclipse生成我的hashCode()方法时,总会使用素数31:
public int hashCode() {
final int prime = 31;
//...
}
参考文献:
这是关于Hashcode的一篇很好的入门文章和关于我如何找到哈希工作的文章(C#但概念是可转移的): Eric Lippert的GetHashCode指南和规则()
只是我正在寻找的一个例子:我可以用一点代表每个奇数,例如对于给定的数字范围(1,10),从3开始:
__PRE__
以下字典可以挤得更对吗？我可以通过一些工作来消除五的倍数,但是以1,3,7或9结尾的数字必须在位数组中存在.希望这能澄清我想要的东西.
我正在寻找最好的算法,检查数字是否是素数,即布尔函数:
__PRE__
我想知道实现此功能的最佳算法.当然,我可以查询一个数据结构.我定义了最好的算法,它是生成数据结构的算法,该数据结构具有最低的内存消耗范围(1,N),其中N是常量.
我在RosettaCode上找到了以下Java代码示例:
public static boolean prime(int n) {
return !new String(new char[n]).matches(".?|(..+?)\\1+");
}
如何.?|(..+?)\\1+匹配素数？
这种方法BigInteger.isProbablePrime()很奇怪; 从文档中,这将告诉一个数字是否是素数的概率1 - 1 / 2^arg,其中arg是整数参数.
它已经存在于JDK很长一段时间了,所以它意味着它必须有用.我在计算机科学和算法(以及数学)方面的有限知识告诉我,知道一个数字是否"可能"是一个素数而不是一个素数并不是真的有意义.
那么,人们想要使用这种方法的可能情况是什么？密码？
实现此功能的最佳方式是什么:
ArrayList generatePrimes(int n)
此函数生成第一个n素数(编辑:where n>1),因此generatePrimes(5)将返回ArrayListwith {2, 3, 5, 7, 11}.(我在C#中这样做,但我很高兴Java实现 - 或任何其他类似的语言(所以不是Haskell)).
我知道怎么写这个函数,但是当我昨晚做到这一点时,它并没有像我希望的那样结束.这是我想出的:
ArrayList generatePrimes(int toGenerate)
{
ArrayList primes = new ArrayList();
primes.Add(2);
primes.Add(3);
while (primes.Count < toGenerate)
{
int nextPrime = (int)(primes[primes.Count - 1]) + 2;
while (true)
{
bool isPrime = true;
foreach (int n in primes)
{
if (nextPrime % n == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
break;
}
else
{
nextPrime …我试图想出一个方法,它接受一个整数并返回一个布尔值来说明数字是否为素数,我不知道多少C; 有人会关心给我一些指示吗？
基本上,我会在C#中这样做:
static bool IsPrime(int number)
{
for (int i = 2; i < number; i++)
{
if (number % i == 0 && i != number)
return false;
}
return true;
}