相关疑难解决方法(0)

我一直在努力学习生成素数的算法,我在维基百科上遇到了阿特金的Sieve.我理解算法的几乎所有部分,除了少数几个.以下是问题:

1. 下面的三个二次方程如何形成？4x ^ 2 + y ^ 2,3x ^ 2 + y ^ 2和3x ^ 2-y2
2. 维基百科中的算法讨论模数为60但我不明白在下面的psudocode中使用的方式/位置.
3. 如何找到这些提醒1,5,7和11？

以下是维基百科的伪代码供参考:

// arbitrary search limit                                                   
limit ? 1000000                                                             

// initialize the sieve                                                     
for i in [5, limit]: is_prime(i) ? false                                    

// put in candidate primes:                                                 
// integers which have an odd number of                                     
// representations by certain quadratic forms                               
for (x, y) in [1, ?limit] × [1, ?limit]:                                    
    n ? 4x²+y²                                                              
    if (n ? limit) and (n mod 12 = 1 or …

我根据维基百科的低效但清晰的伪代码写了一篇非常天真的Atna Sieve实现.我最初在MATLAB中编写了算法,它省略了5作为素数.我也用Python编写了算法,结果相同.

从技术上讲,我知道为什么要排除5; 在步骤中n = 4*x^2 + y^2,当x == 1且y == 1时n == 5.这只发生一次,因此5从素数转换为非素数并且从不翻转.

为什么我的算法与维基百科上的算法不匹配？虽然我做了一些表面调整(例如,在每次迭代中只计算一次x ^ 2,在第一个等式中使用时存储mod(n,12)的值等),但它们不应该改变逻辑.算法.

我阅读了几篇 与阿特金筛选有关的讨论 ,但我不知道在我的实现中产生问题的区别是什么.

Python代码:

def atkin1(limit):
    res = [0] * (limit + 1)
    res[2] = 1
    res[3] = 1
    res[5] = 1

    limitSqrt = int(math.sqrt(limit))
    for x in range(1, limitSqrt+1):
        for y in range(1, limitSqrt+1):
            x2 = x**2
            y2 = y**2
            n = 4*x2 + y2
            if n == 5:
                print('debug1')
            nMod12 …

我不知道这是否可能，但我只是想问一下。我的数学和算法技能有点让我失望：P

问题是我现在有这个类可以生成达到一定限制的素数：

public class Atkin : IEnumerable<ulong>
{
    private readonly List<ulong> primes;
    private readonly ulong limit;

    public Atkin(ulong limit)
    {
        this.limit = limit;
        primes = new List<ulong>();
    }

    private void FindPrimes()
    {
        var isPrime = new bool[limit + 1];
        var sqrt = Math.Sqrt(limit);

        for (ulong x = 1; x <= sqrt; x++)
            for (ulong y = 1; y <= sqrt; y++)
            {
                var n = 4*x*x + y*y;
                if (n <= limit && (n % 12 == 1 || n …

我正在尝试使用Mutithreading实现Sieve Of Eratosthenes.这是我的实现:

using System;
using System.Collections.Generic;
using System.Threading;

namespace Sieve_Of_Eratosthenes 
{
    class Controller 
        {
        public static int upperLimit = 1000000000;
        public static bool[] primeArray = new bool[upperLimit];

        static void Main(string[] args) 
        {
        DateTime startTime = DateTime.Now;

        Initialize initial1 = new Initialize(0, 249999999);
        Initialize initial2 = new Initialize(250000000, 499999999);
        Initialize initial3 = new Initialize(500000000, 749999999);
        Initialize initial4 = new Initialize(750000000, 999999999);

        initial1.thread.Join();
        initial2.thread.Join();
        initial3.thread.Join();
        initial4.thread.Join();

        int sqrtLimit = (int)Math.Sqrt(upperLimit);

        Sieve sieve1 = new Sieve(249999999);
        Sieve sieve2 = new Sieve(499999999);
        Sieve …