Сумма простых чисел меньше двух миллионов. Сито Эратосфена

Возникли небольшие проблемы с решением задачи: «Вычислите сумму простых чисел меньше двух миллионов». Я использую метод «Решета Эратосфена». Мой метод отлично работает для нахождения простых чисел до сотни, но когда я пытаюсь найти сумму простых чисел до 2 000 000, я получаю неверный ответ.

#include <iostream>

using namespace std;
long long unsigned int number[2000008];
int x=2000000LLU;
int sum()
{
    int s=0LLU; //stores sum
    for(int y=2; y<=x; y++) //add all the numers in the array from 2 to 2 million
    {
        s+=number[y];
    }
    return s;
}

int main()
{
    int k=2;
    for(int i=2; i<=x; i++) //fills in numbers from 2 to 2 million in the array
    {
        number[i]=i;
    }
    for(int j=2; j<=x; j+=1) //starts eliminating multiples of prime numbers from the grid
    {
        if(number[j]!=0) //moves through the grid till it finds a number that hasnt been crossed out. ie. isnt zero                            
        {
            for(int y=j+j; y<=x; y+=j) //when it finds a number, it removes all subsequent multiples of it
            {
                number[y]=0;
            }
        }

    }  
    cout<<endl<<"done"; //shows that the loop has been completed
    cout<<sum(); //outputs the sum of the grid
    return 0;
}

c++ sieve-of-eratosthenes
person viraj    schedule 30.05.2011    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Я не уверен, что для хранения ответа достаточно int... Оно может быть больше 32-битного значения. Попробуйте везде использовать long long.

person Omri Barel    schedule 30.05.2011
comment
Этого было достаточно, чтобы сохранить решение для меня. - person aligray; 30.05.2011
comment
@aligray: Это зависит от размера вашего int, который зависит от платформы. То же самое касается long, тогда как long long должен иметь возможность хранить не менее 64 бит на любой платформе. Ответ представляет собой 38-битное значение. - person Omri Barel; 30.05.2011
comment
@omrib Упс, хотел сказать, что long long было достаточно. - person aligray; 30.05.2011
comment
ответ, который я получаю: 1179908154, фактический ответ: 142913828922 - person viraj; 30.05.2011
comment
@viraj: уверен, что это ответ после изменения int на long long для хранения суммы, как было предложено? Вы пробовали это? - person Doc Brown; 30.05.2011
comment
@viraj: вы не изменили эту строку int s=0LLU; //stores sum. Сумма должна быть long long. И функция также должна возвращать long long. - person Omri Barel; 30.05.2011
comment
Хорошо. Теперь я получаю правильный ответ. Спасибо :) Хотя добавление LLU в конец было эквивалентно объявлению его длинным длинным. Кстати, могу я добавить третью длинную? Редактировать: Хорошо, я не могу. :П - person viraj; 30.05.2011
comment
LLU просто превращает литерал в unsigned long long. Но затем вы берете это значение и сжимаете его в меньшую переменную. Разумный компилятор (с разумным уровнем предупреждений) должен предупредить вас, что вы делаете что-то рискованное. - person Omri Barel; 30.05.2011

arrow_upward
1
arrow_downward

эффективно используя Sieve of Eratosthenes, я решил проблему, вот мой код, он сильно оптимизирован

public class SumOfPrime {

    static void findSum()
    {
        long i=3;
        long sum=0;
        int count=0;
        boolean[] array = new boolean[2000000];
        for(long j=0;j<array.length;j++)
        {
         if((j&1)==0)
          array[(int)j]=false;   
         else    
         array[(int)j]=true;
        }
        array[1]=false;
        array[2]=true;
        for(;i<2000000;i+=2)
        { 
            if(array[(int)i] & isPrime(i))
            {   
                array[(int)i]=true;
                //Sieve of Eratosthenes
                for(long j=i+i;j<array.length;j+=i)
                    array[(int)j]=false;
            }
        }
        for(int j=0;j<array.length;j++)
        {
            if(array[j])
            {   
             //System.out.println(j);
             count++;   
             sum+=j;
            }
        }   
        System.out.println("Sum="+sum +" Count="+count);
    }
    public static boolean isPrime(long num)
    {
        boolean flag=false;
        long i=3;
        long limit=(long)Math.sqrt(num);
        for(;i<limit && !(flag);i+=2)
        {
            if(num%i==0)
            {
                flag=false;
                break;
            }   
        }
        if(i>=limit)
         flag=true;
        return flag;
    }

    public static void main(String args[])
    {
        long start=System.currentTimeMillis();
        findSum();
        long end=System.currentTimeMillis();
        System.out.println("Time for execution="+(end-start)+"ms");
    }

}

и выход

Sum=142913828922 Count=148933
Time for execution=2360ms

если у вас есть сомнения, пожалуйста, скажите

person Akhil Jain    schedule 07.12.2012