Я не знаю, почему это занимает вечность для больших чисел Я пытаюсь решить задачу 10 в Project Euler (https://projecteuler.net/problem=10). Кто-нибудь может мне помочь?

Она находит первое простое число и перебирает все его факторы, затем переходит к следующему простому числу и так далее.

long sum=0;
        int howmanyChecked = 1;
        int target = 1000000;
        int index = -1;
        List numbers = new List(target);
        List Isprime = new List(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

aaarianme

Ответов: 3

Ответы (3)

Применим несколько простых оптимизаций:

  • список чисел не следует использовать, поскольку каждое число может быть вычислено на основе индекса
  • .
  • упрощенная инициализация 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();

Попробуйте с этим:

#include 
#include 
#include 
#include 

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;
}

Делайте SoE (Решето Эратосфена) до n=2000000, если вы хотите экономить память 2000000/16 = 62500 байт, так как вам нужен всего один бит на нечетное число). Вы можете сделать сумму во время заполнения SoE.

Ваше описание - это SoE, но у вас слишком много кода для SoE... мое простое SoE-решение для этого - всего 11 строк форматированного C++ кода, где половина - это объявление переменных:

const DWORD N=2000000; // ~ 36 мс
const DWORD M=N>>1; // храним только нечетные значения из 3,5,7,...
char p[M]; // p[i] -> является ли 1+i+i простым? (карта факторов)
DWORD i,j,k,ss=0,n=0x10000000-N;
uint<2> s=2;
p[0]=0; for (i=1;i>1;i=n) { s+=DWORD(ss); ss=0; }}
    for(k=i+j;k

где DWORD - это беззнаковый 32-битный int, а uint<2> - 64-битный беззнаковый int (так как я все еще на 32-битном компиляторе, поэтому я делаю сумму так странно). Как видите, у вас получилось в 3 раза больше кода, чем нужно.

Использование IsPrime без мемоизации слишком медленно, но даже с мемоизацией никогда не сможет победить SoE. см.:

btw. Я собрал свои проекты Эйлера в одном приложении, где я делаю SoE до 10^7, что создает список всех простых до 10^7, что занимает 130 мс на моем довольно старом ПК, и это затем используется для всех задач Эйлера, связанных с простыми (что ускоряет их, так что первые 40 задач завершаются менее чем за 1 сек), что для этого случая (другой код решения) занимает 0.7 мс.

Чтобы избежать переполнения суммы на 64-битной арифметике.

Также использование динамических списков без предварительного распределения является медленным. В любом случае они вам не нужны.

2022 WebDevInsider