Numbers of Interest 2

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

Example:

Input:  n = 3
Output: 1

Approach

C++

#include <bits/stdc++.h>
using namespace std;
int prime(int n)
{
    if (n % 2 == 0)
        return 2;
    for (int i = 3; i * i <= n; i++)
        if (n % i == 0)
            return i;
    return n;
}
int factor(int n)
{
    int ans = 0;
    for (int i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            if (i != n && n / i == i)
                ans += i;
            else
            {
                if (i != n)
                    ans += i;
                if (n / i != n)
                    ans += n / i;
            }
        }
    }
    return ans;
}
int main()
{

    int arr[100001] = {0};
    for (int i = 2; i <= 100000; i++)
    {
        if (i % 2 == 0)
            arr[i] = 2;
        else
            arr[i] = prime(i);
    }
    int brr[100001] = {0};
    for (int i = 1; i <= 100000; i++)
        brr[i] = factor(i);

    int n = 3;

    int f[n + 1], g[n + 1];
    f[0] = 0;
    int x[n];
    g[0] = 0;
    x[0] = x[1] = 0;
    int y[n];
    y[0] = y[1] = 0;
    for (int i = 1; i <= n; i++)
        f[i] = f[i - 1] + arr[i];
    for (int i = 1; i <= n; i++)
        g[i] = g[i - 1] + brr[i];

    int ans = (f[n] + g[n]) % n;
    cout << ans << "\n";

    return 0;
}