Problem 3: Non-Primes

Points:

Small Case: 8 Answer: 11007

Large Case: 16 Answer: 521907490474536813

Let n be a non-prime number and x be its smallest divisor(not 1) and f(n) be a function such that f(n) = x*n.

The problem is to find the function s(n) which is defined as the sum of all f(i) for all possible i less than and equal to n.

e.g for s(10)=83

Small Case: n=100

Large Case: n=10^8

Solution:

For all the multiples(j) of numbers(i)(2 to sqrt(n)) which haven't occured previosuly, i*j is added to the answer.

#include<iostream>

#include<cmath>

using namespace std;

bool ar[100000001]={0};

int main()

{

unsigned long long int i,j;

unsigned long long int s=0;

unsigned long long int n;

cin>>n;

for(i=2;i<=sqrt(n);i++)

{

	if(ar[i]==0)

	{

		for(j=i*i;j<=n;j+=i)

		{

			if(ar[j]==0)

				s+=(i*j);

			ar[j]=1;

		}

	}

	

}

cout<<s;



return 0;

}