算法 - 这个Erastothenes解决方案有什么问题

我想我会创建自己的Sieve算法实现来更快地找到素数。令人惊讶的是，这没有通过一些测试。算法 - 这个Erastothenes解决方案有什么问题

这是我在Ruby中的算法，用于确定数字是否为素数。

def prime?(n) 
    primes = [2,3,5,7,9,11,13,17] 
    primes.include?(n) || primes.none? { |p| n % p == 0 } 
end

算法如何工作是你把第一对夫妇的素数，我把前8个是安全的。然后，我会去除这些素数的所有倍数，因为它们不可能是素数。

因此，所有其他的数字必须是素

我震惊地发现我的测试失败，我忽略了一些数字。这怎么可能？我完全遵循算法。

来源

2015-12-30 Richard Hamilton

任何不在您的有限列表中的质数产品将被您的函数错误地归类为质数。例如，19 * 19或19 * 23或19 * 29 * 37。 –

你没有追随Erastothenes的方法。 –

答案是你没有完全遵循算法。而且，一旦你清除了前8个素数的所有倍数，所有其他数字都是素数，这是不正确的。 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_and_varariants – jrochkind

测试给定数n你需要检查它是否是整除的任何素数<的素性= sqrt（n）。既然你已经硬连线到17的素数，你的算法将只适用于值为n < = 17 。

最重要的是，您在“素数”列表中包含了9个。这不应该影响你的测试，除了值9本身，因为任何被9整除的东西也可以被3整除，但它很顽皮。

来源

2015-12-30 00:43:31 pjs

@CoderX我没有发布任何方法，我已经解释了他的方法的局限性。你不了解什么部分的解释？ – pjs

Erastothenes的方法不受限于<= 17 * 17。它只会找到下一个最小的数字，并删除所有小于n的数字的倍数。 –

@CoderX他的实现受限于17 * 17。他可以测试素数的最大数量受限于他已知的最大素数的平方。 – pjs

首先，你已经在质数列表中包含了9个。 9不是素数。请尝试以下方法。

查找所有数字以上的素数。从最小的素数开始，2.
标记2作为素数，并删除所有倍数2. 2.
接下来看哪个是最小的数字没被删除。它是3.打印3作为素数，并删除3的所有倍数小于n。

然后再选择下一个最小的数不能删除线了，等

def primeSeive(n) 
    while primes[index]**2 <= primes.last 
     prime = primes[index] 
     primes = primes.select { |x| x == prime || x%prime != 0 } 
     index += 1 
end

来源

2015-12-30 00:43:21

我不是很擅长ruby，但看起来你并没有遵循这个算法。此外，你添加9作为质数是不正确的。

筛算法首先只需要作为素数。

伪：

Sieve(n) { 
    a[1] := 0       
    for i := 2 to n do a[i] := 1 
    p := 2 
    while p2 < n do { 
    j := p2 
    while (j < n) do {    
     a[j] := 0 
     j := j+p 
    } 
    repeat p := p+1 until a[p] = 1 
    } 
    return(a) 
}

这里甲是阵列，其中的索引值指示primeness。 for not prime， for prime。在而循环标记素数倍数和最后挑选下一个素数重复部分。

来源

2015-12-30 05:31:20

算法 - 这个Erastothenes解决方案有什么问题

回答

相关问题