UVA 10200 - Prime Time solution

problem link-click here

Solving this problem i have learnt a new technique which is how to reduce time complexity and make it o(1) from o(n^3) that means i get output at constant time. i have used cumulative sum to solve this problem. now obviously you must be curious to know what actually cumulative sum is. try google for getting cumulative sum.

an accepted code is as follows:

#include<bits/stdc++.h>
#define s 10500
using namespace std;

vector<int> v;
bool arr[s];

void sieve()
{
    v.push_back(2);

    for(int i=3;i<=s;i+=2)
    {
        if(arr[i]==0)
        {
            v.push_back(i);

            for(int j=3;i*j<=s;j+=2)
            {
                arr[i*j]=1;
            }
        }
    }
}

int prime(long long int n)
{
    int i=0;

    while(v[i]*v[i]<=n)
    {
        if(n%v[i]==0)
        {
            return 0;
        }

        i++;
    }

    return 1;
}

int main()
{
    sieve();

    vector<double> v1;
    long long int n;

    for(int i=0;i<=10001;i++)
    {
        n=i*i+i+41;
        v1.push_back(prime(n));

        if(i>0)
        {
          v1[i]=v1[i]+v1[i-1];
        }
    }

    int a,b;
    double e;

    while(scanf("%d%d",&a,&b)==2)
    {
        if(a==0)
        {
            printf("%.2lf\n",((v1[b]-0)/(abs(b-a)+1))*100)+1e-8;
        }
        else
        {
          e=((v1[b]-v1[a-1])/(abs(b-a)+1))*100+1e-8;
          printf("%.2lf\n",e);
        }
    }

    return 0;
}