一位同事刚刚告诉我,C#字典集合按照与散列有关的神秘理由按素数调整大小.而我当前的问题是,"它如何知道下一个素数是什么？他们是故事还是一个巨大的表格或动态计算？这是一个可怕的非确定性运行时插入导致调整大小"
所以我的问题是,给定N,这是一个素数,计算下一个素数的最有效方法是什么？
假设您有两个列表A = [a_1, a_2, ..., a_n]和B = [b_1, b_2, ..., b_n]整数.我们说A是潜在的,可分割的B,如果有一个置换B,使得a_i整除b_i所有i.那么问题是:是否有可能重新排序(即置换)B以便a_i可以被b_i所有人整除i？例如,如果你有
A = [6, 12, 8]
B = [3, 4, 6]
那么答案是True,因为B可以重新排序是B = [3, 6, 4],然后我们就会有a_1 / b_1 = 2,a_2 / b_2 = 2和a_3 / b_3 = 2,所有这一切都是整数,因此A是潜在的,整除B …
只是为了澄清,这不是一个功课问题:)
我想找到我正在建造的数学应用程序的素数并且遇到了Eratosthenes的Sieve方法.
我用Python编写了它的实现.但它非常慢.比方说,如果我想找到不到200万的所有素数.大约需要20分钟.(此时我停了下来).我怎样才能加快速度呢？
def primes_sieve(limit):
limitn = limit+1
primes = range(2, limitn)
for i in primes:
factors = range(i, limitn, i)
for f in factors[1:]:
if f in primes:
primes.remove(f)
return primes
print primes_sieve(2000)
更新: 我最终对这段代码进行了分析,发现花了很多时间从列表中删除一个元素.考虑到它必须遍历整个列表(最坏情况)才能找到元素然后将其删除然后重新调整列表(可能还有一些副本继续？),这是相当容易理解的.无论如何,我把字典列表删掉了.我的新实施 -
def primes_sieve1(limit):
limitn = limit+1
primes = dict()
for i in range(2, limitn): primes[i] = True
for i in primes:
factors = range(i,limitn, i)
for f in factors[1:]:
primes[f] = False
return [i for i in primes if primes[i]==True]
print primes_sieve1(2000000)
这不是作业,我只是好奇.
INFINITE是这里的关键词.
我希望在primes()中使用它作为p.我相信这是Haskell中的内置函数.
所以,答案不能像"Just do a Sieve"那样天真.
首先,您不知道将消耗多少连续素数.好吧,假设你可以一次编制100个.您是否会使用相同的Sieve方法以及素数公式的频率？
我更喜欢非并发方法.
感谢您阅读(和写作;))!
Eclipse 3.5有一个非常好的功能来生成Java hashCode()函数.它会产生例如(稍微缩短:)
class HashTest {
int i;
int j;
public int hashCode() {
final int prime = 31;
int result = prime + i;
result = prime * result + j;
return result;
}
}
(如果类中有更多属性,result = prime * result + attribute.hashCode();则对每个附加属性重复.对于int.可以省略.hashCode().)
这似乎很好,但选择31为素数.它可能来自Java String的hashCode实现,它被用于性能原因,这些原因在引入硬件乘法器之后很久就消失了.对于i和j的小值,这里有许多哈希码冲突:例如(0,0)和(-1,31)具有相同的值.我认为这是一个Bad Thing(TM),因为经常出现小值.对于String.hashCode,您还会发现许多具有相同哈希码的短字符串,例如"Ca"和"DB".如果选择大素数,如果选择素数,此问题就会消失.
所以我的问题是:选择什么是好的素数？你用什么标准来找到它？
这是一个普遍的问题 - 所以我不想给i和j一个范围.但我认为在大多数应用中,相对较小的值比较大的值更常出现.(如果你有大的值,素数的选择可能不重要.)它可能没有多大区别,但更好的选择是一种简单明了的方法来改善这一点 - 那么为什么不这样做呢？Commons lang HashCodeBuilder也提出了奇怪的小值.
(澄清:这不是重复为什么String中的Java的hashCode()使用31作为乘数？因为我的问题不关心JDK中31的历史,而是关于新代码中更好的值使用相同的基本模板.没有任何答案试图回答.)
可能重复:
如何确定一个数字是否是正则表达式的素数？
此页面声称此正则表达式发现非素数(并通过反例:素数):
/^1?$|^(11+?)\1+$/
这怎么找到素数？
我想打印前10000个素数.任何人都可以给我最有效的代码吗？澄清:
假设简单的统一散列,即任何给定值同样地散列到散列的任何槽中.为什么使用大小为127而不是128的表更好？我真的不明白2号码的力量有什么问题.或者它实际上如何产生任何差异.
使用除法时,我们通常会避免使用某些m值(表大小).例如,m不应该是2的幂,因为如果m = 2 ^ p,则h(k)只是k的p个最低位.
假设可能的元素只在1和10000之间,我选择表格大小为128. 127如何才能更好？所以128是2 ^ 6(1000000),127是0111111.这有什么区别？所有数字(当经过哈希处理时)仍然是127的p的最低位数.我弄错了吗？
我正在寻找一些例子,因为我真的不明白为什么这么糟糕.非常感谢提前!
PS:我知道: 哈希表:为什么大小应该是素数？
在Javascript中我怎么能找到0到100之间的素数？我已经考虑过了,我不知道如何找到它们.我想做x%x,但我发现了明显的问题.这是我到目前为止所做的:但不幸的是,这是有史以来最糟糕的代码.
var prime = function (){
var num;
for (num = 0; num < 101; num++){
if (num % 2 === 0){
break;
}
else if (num % 3 === 0){
break;
}
else if (num % 4=== 0){
break;
}
else if (num % 5 === 0){
break;
}
else if (num % 6 === 0){
break;
}
else if (num % 7 === 0){
break;
}
else if (num % 8 === 0){
break;
}
else if (num …我试图找到检查给定数字是否为素数的最快方法(在Java中).以下是我提出的几种素性测试方法.有没有比第二个实现更好的方法(isPrime2)？
public class Prime {
public static boolean isPrime1(int n) {
if (n <= 1) {
return false;
}
if (n == 2) {
return true;
}
for (int i = 2; i <= Math.sqrt(n) + 1; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public static boolean isPrime2(int n) {
if (n <= 1) {
return false;
}
if (n == 2) {
return true;
}
if (n % 2 == …