'Summation of primes' 耗时太长

Question

我不知道为什么这对大数来说要花很长时间我正在尝试解决欧拉计划 (https://projecteuler.net/problem=10) 中的问题 10。有人可以帮我吗？

它找到第一个素数并与它的所有因子相交，然后移动到下一个素数，依此类推。

long sum=0;
        int howmanyChecked = 1;
        int target = 1000000;
        int index = -1;
        List<int> numbers = new List<int>(target);
        List<bool> Isprime = new List<bool>(target);
        for(int i=2;i<=target;i++)
        {
            numbers.Add(i);
            Isprime.Add(true);
        }
        while (1 > 0)
        {
            index = Isprime.IndexOf(true, index + 1);

            int Selected = numbers[index];
            howmanyChecked++;


            sum += Selected;
            //Console.WriteLine($"selected prime number is {Selected}");
            //int startfrom =numbers.IndexOf(Selected * Selected);
            if (Selected >= target / 2)
            {
                Console.WriteLine("ss");
                for(int i=index+1;i<target-1;i++)

                {
                    if(Isprime[i]==true)
                    {
                        Console.WriteLine(numbers[i].ToString());
                        sum += numbers[i];
                    }
                }
                Console.WriteLine($"the sum of all prime nubers below {target} is {sum} tap to continue");
                Console.ReadLine();
                break;


            }
            else
            {
                for (int i = Selected; i * Selected <= target; i++)
                {
                    int k = numbers.IndexOf(i * Selected);
                    if (k == -1)
                        break;
                    if (Isprime[k] == true)
                    {
                        Isprime[numbers.IndexOf(i * Selected)] = false;
                        howmanyChecked++;
                        //Console.WriteLine($"Checked number is {Selected * i} and we have counted {howmanyChecked} numbers");
                    }



                }
            }
            if (howmanyChecked == target || index==target)
                break;
            
        }


        Console.ReadLine();

Answer 1

应用一些简单的优化：

list numbers不应使用，因为每个数字都可以根据索引计算
Isprime.

1'000'000 得到：

the sum of all prime numbers below 1000000 is 37548466742 tap to continue

long sum = 0;
int howmanyChecked = 1;
int target = 1000000;
int index = -1;
var Isprime = Enumerable.Repeat(true, target).ToArray();

while (1 > 0)
{
    index = Array.IndexOf(Isprime, true, index + 1);

    int Selected = index + 2;
    howmanyChecked++;


    sum += Selected;
    //Console.WriteLine($"selected prime number is {Selected}");
    //int startfrom =numbers.IndexOf(Selected * Selected);
    if (Selected >= target / 2)
    {
        Console.WriteLine("ss");
        for (int i = index + 1; i < target - 1; i++)

        {
            if (Isprime[i] == true)
            {
                Console.WriteLine(i + 2);
                sum += i + 2;
            }
        }
        Console.WriteLine($"the sum of all prime nubers below {target} is {sum} tap to continue");
        Console.ReadLine();
        break;
    }
    else
    {
        for (int i = Selected; i * Selected <= target; i++)
        {
            int k = i * Selected - 2;
            if (k < 0)
                break;
            if (Isprime[k] == true)
            {
                Isprime[k] = false;
                howmanyChecked++;
                //Console.WriteLine($"Checked number is {Selected * i} and we have counted {howmanyChecked} numbers");
            }
        }
    }
    if (howmanyChecked == target || index == target)
        break;

}

Console.ReadLine();

Answer 2

做 SoE（Eratosthenes 筛法）最多 n=2000000 以防您想要提高内存效率 2000000/16 = 62500 字节，因为您每次只需要一位奇数）。您可以在填充 SoE.

的同时进行求和

你的描述是一个 SoE，但你的 SoE 代码太多了……我的简单 SoE 解决方案只是 11 行格式化的 C++ 代码，其中一半是变量声明：

const DWORD N=2000000;                      // ~ 36 ms
const DWORD M=N>>1;                         // store only odd values from 3,5,7,...
char p[M];                                  // p[i] ->  is 1+i+i prime? (factors map)
DWORD i,j,k,ss=0,n=0x10000000-N;
uint<2> s=2;
p[0]=0; for (i=1;i<M;i++) p[i]=1;
for(i=3,j=i>>1;i<N;i+=2,j++)
    {
    if (p[j]==1) { ss+=i; if (ss>=n) { s+=DWORD(ss); ss=0; }}
    for(k=i+j;k<M;k+=i) p[k]=0;
    } s+=DWORD(ss);
// s holds the answer 142913828922

其中 DWORD 是 unsigned 32 位 int，uint<2> 是 64 位 unsigned int（因为我仍在使用 32 位编译器，这就是为什么我如此奇怪地求和）。如您所见，您获得的代码可能比所需代码多 3 倍。

在没有记忆的情况下使用 IsPrime 太慢了，但即使有记忆也永远无法击败 SoE。见：

Prime numbers by Eratosthenes quicker sequential than concurrently?

顺便说一句。我在单个应用程序中获得了我的 Euler 项目，我在其中执行 SoE 直到 10^7，它创建了所有素数的列表，直到 10^7 这需要 130 ms在我相当旧的 PC 上，然后用于所有与素数相关的欧拉问题（这加快了它们的速度，因此前 40 个问题在 1 秒内完成），对于这种情况（不同的解决方案代码）需要 0.7 ms.

避免 64 位算术求和溢出。

使用没有预分配的动态列表也很慢。反正你不需要它们。

Answer 3

试试这个：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

int main()
{
    int  n,i,i1,imax;
    long sumprime;
    bool *prime5mod6,*prime1mod6;

    n=2000000;
    
    imax=(n-n%6)/6+1;
    prime5mod6 = (bool *) calloc(imax+1,sizeof(bool));
    prime1mod6 = (bool *) calloc(imax+1,sizeof(bool));
    
    sumprime=5;         
    for(i=1;(6*i-1)*(6*i-1)<=n;i++){
        if(prime5mod6[i]==false){
             sumprime=sumprime+6*i-1;
             for(i1=6*i*i;i1 <= imax+2*i;i1+=(6*i-1)){
                if(i1<=imax)
                   prime5mod6[i1]=true;
                prime1mod6[i1-2*i]=true;        
             }
        }
        if(prime1mod6[i]==false){
             sumprime=sumprime+6*i+1;
             for(i1 = 6*i*i;i1<=imax;i1+=(6*i+1)){
                prime5mod6[i1]=true;
                if(i1<=imax-2*i)
                    prime1mod6[i1+2*i]=true;        
             }
        }
    }

    for(i1=i;i1<=imax-1;i1++){
        if(prime5mod6[i1]==false)
             sumprime=sumprime+6*i1-1;
        if(prime1mod6[i1]==false)
             sumprime=sumprime+6*i1+1;
    }
    if(prime5mod6[imax]==false && n%6==5)
             sumprime=sumprime+6*imax-1;
    if(prime1mod6[imax-1]==false && n%6==0)
             sumprime=sumprime-(6*(imax-1)+1);

    printf("\nPrime sum: %ld",sumprime);
    free(prime5mod6);
    free(prime1mod6);
    return 0;
}

'Summation of primes' 耗时太长

'Summation of primes' takes too long

c#

algorithm

math

primes