HackerEarth Numbers of Interest 2 problem solution

YASH PAL,
In this HackerEarth Number of Interest 2 problem solution After solving Reese’s first problem Harold thought he had proven himself. But Reese wasn’t convinced so he gave Harold another query. He told Harold to find the nth term of the sequence given by the equation.
a[n]=( f[n] + g[n] ) % n
where, f[n] = f[n-1] + x(n) ; where x(n) = smallest prime factor of n.
and g[n] = g[n-1] + y(n) ; where y(n) = sum of all natural numbers p less than n which follow that n % p == 0
Given : x(0) = x(1) = y(0) = y(1) = 0
HackerEarth Numbers of Interest 2 problem solution

HackerEarth Numbers of Interest 2 problem solution.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long f[1000005];
long long ans[1000005];
long long arr[1000005];
void markMultiples(long long a)
{
    long long i=2,num;
    while((num=i*a)<=1000005)
    {
        if(arr[num]==0)arr[num]+=a;
        ++i;
    }
}

void SieveOfEratosthenes()
{
           for (long long i=2;i<1000005;++i)
        {
            if (arr[i]==0)
            {
                arr[i]=(arr[i-1]+i);
                markMultiples(i);
            }
            else
                arr[i]+=arr[i-1];
        }
}

int main()
{
    SieveOfEratosthenes();
    memset(f,0,sizeof(f));
    memset(ans,0,sizeof(ans));
    long long i=0,j=0;
    for(i=1;i<=(1000002/2);i++)
    {
        for(j=i+i;j<1000002;j+=i)
        {
            f[j]+=i;
        }
    }
    for(i=2;i<1000002;i++)
        ans[i]=ans[i-1]+f[i];
    int t;
    scanf("%d",&t);
    while(t--)
        {
        long long n;scanf("%lld",&n);
        printf("%lldn",(ans[n]+arr[n])%n);
        }

    return 0;
}
coding problems solutions