c программа для поиска суммы первых 1000 простых чисел

Question

Я хочу напечатать сумму первых 1000 простых чисел.Я не знаю, правильна ли следующая реализация и где она неправильна.Кроме того, как я могу оптимизировать эту реализацию, которая требуется для дополнительного курса?

#include<stdio.h>
#include<math.h>
int prime(int no,int lim)
{
    int i=2,flag=0;
    for(;i<=lim;i++)
    {
        if(no%i==0)
        {   
            flag=1;     
        }
    }
    return flag ;
}

int main()
{
    int i=4,count=2,j,k,l,n=4;
    double sum=5.0;

    for(;count<=1000;)
    {   
        j=sqrt(i);
        k=prime(i,j);
        if(k==0)
        {
            //printf("\n%d",i);
            sum+=(double)i;
            //for(l=0;l<100000;l++);//just to reduce speed of the program

            count++;
        }
    i++;

}
printf("\n%f",sum);
        return 0;   
}

Answer 1

Я не знаю, правильна ли следующая реализация и где она неправильна.

Реализация правильная, за исключением ошибки "off-by-one": Так как countэто число простых чисел, которые уже были учтены, условие цикла count<=1000 заставляет цикл запускаться еще раз, когда 1000 простых чисел уже суммировано, добавляя простое число 1001.Правильно это: count<1000.

Answer 2

Для оптимизации вашего кода лучше использовать Сито Эратосфена , чтобы сгенерировать простое число до вашего лимита, а затем добавить эти простые числа.Чтобы узнать, как работает сито , прочитайте эту статью.