Блог

Главная - Вопросы по программированию - Сумма простых чисел меньше двух миллионов. Сито Эратосфена

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

#c #sieve-of-eratosthenes

#c #сито эратосфена

Вопрос:

Возникли небольшие проблемы с решением задачи: «Вычислите сумму простых чисел меньше двух миллионов». Я использую метод «Сита Эратосфена». Мой метод отлично работает для нахождения простых чисел до ста, но когда я пытаюсь найти сумму простых чисел до 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;
}

Ответ №1:

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

Комментарии:

1. Этого было достаточно, чтобы сохранить решение для меня.

2. @aligray: Это зависит от размера вашего int , который зависит от платформы. То же самое касается long , тогда как long long должно быть способно содержать не менее 64 бит на любой платформе. Ответом является 38-битное значение.

3. @omrib Упс, хотел сказать, long long было достаточно.

4. я получаю ответ: 1179908154 фактический ответ: 142913828922

5. @viraj: уверен, что это ответ после изменения «int» на «long long» для сохранения суммы, как было предложено? Вы пробовали это?

Ответ №2:

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

 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((jamp;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] amp; 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 amp;amp; !(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

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