# Sum of largest prime factor of each number less than equal to n

Given a non-negative integer n. The problem is to find the sum of the largest prime factor of each number less than equal to n.

Examples:

```Input : n = 10
Output : 32
Largest prime factor of each number
Prime factor of 2 = 2
Prime factor of 3 = 3
Prime factor of 4 = 2
Prime factor of 5 = 5
Prime factor of 6 = 3
Prime factor of 7 = 7
Prime factor of 8 = 2
Prime factor of 9 = 3
Prime factor of 10 = 5

Sum = (2+3+2+5+3+7+2+3+5) = 32

Input : n = 12
Output : 46
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Algorithm:

```sumOfLargePrimeFactor(n)
Declare prime[n+1] and initialize all value to 0
Initialize sum = 0
max = n / 2

for p = 2 to max
if prime[p] == 0 then
i = p*2
while i <= n
prime[i] = p
i = i + p

for p = 2 to n
if prime[p] then
sum = sum + prime[p]
else
sum = sum + p

return sum
```

## C++

 `// C++ implementation to find sum of largest prime factor ` `// of each number less than equal to n ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// function to find sum of largest prime factor ` `// of each number less than equal to n ` `int` `sumOfLargePrimeFactor(``int` `n) ` `{ ` `    ``// Create an integer array "prime[0..n]" and initialize ` `    ``// all entries of it as 0. A value in prime[i] will ` `    ``// finally be 0 if 'i' is a prime, else it will  ` `    ``// contain the largest prime factor of 'i'. ` `    ``int` `prime[n+1], sum = 0; ` `    ``memset``(prime, 0, ``sizeof``(prime)); ` `    ``int` `max = n / 2;  ` `  `  `    ``for` `(``int` `p=2; p<=max; p++) ` `    ``{ ` `        ``// If prime[p] is '0', then it is a  ` `        ``// prime number ` `        ``if` `(prime[p] == 0) ` `        ``{ ` `            ``// Update all multiples of p ` `            ``for` `(``int` `i=p*2; i<=n; i += p) ` `                ``prime[i] = p; ` `        ``} ` `    ``} ` `  `  `    ``// Sum up the largest prime factor of all ` `    ``// the numbers ` `    ``for` `(``int` `p=2; p<=n; p++) ` `    ``{ ` `        ``// if 'p' is a non- prime number then ` `        ``// prime[p] gives its largesr prime ` `        ``// factor ` `        ``if` `(prime[p]) ` `             ``sum += prime[p]; ` `            `  `        ``// 'p' is a prime number          ` `        ``else` `             ``sum += p; ` `    ``} ` `     `  `    ``// required sum ` `    ``return` `sum;       ` `} ` ` `  `// Driver program to test above ` `int` `main() ` `{ ` `    ``int` `n = 12; ` `    ``cout << ``"Sum = "` `         ``<< sumOfLargePrimeFactor(n); ` `    ``return` `0;          ` `} `

## Java

 `// Java implementation to find sum ` `// of largest prime factor of each ` `// number less than equal to n ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `GFG { ` `     `  `    ``// function to find sum of largest ` `    ``// prime factorof each number  ` `    ``// less than equal to n ` `    ``static` `int` `sumOfLargePrimeFactor(``int` `n) ` `    ``{ ` `        ``// Create an integer array "prime[0..n]"  ` `        ``// and initialize all entries of it as 0. ` `        ``// A value in prime[i] will finally be 0  ` `        ``// if 'i' is a prime, else it will contain ` `        ``// the largest prime factor of 'i'. ` `        ``int` `prime[] = ``new` `int``[n + ``1``], sum = ``0``; ` `        ``Arrays.fill(prime, ``0``); ` `        ``int` `max = n / ``2``;  ` `     `  `        ``for` `(``int` `p = ``2``; p <= max; p++) ` `        ``{ ` `            ``// If prime[p] is '0', then it is a  ` `            ``// prime number ` `            ``if` `(prime[p] == ``0``) ` `            ``{ ` `                ``// Update all multiples of p ` `                ``for` `(``int` `i = p * ``2``; i <= n; i += p) ` `                    ``prime[i] = p; ` `            ``} ` `        ``} ` `     `  `        ``// Sum up the largest prime factor of all ` `        ``// the numbers ` `        ``for` `(``int` `p = ``2``; p <= n; p++) ` `        ``{ ` `            ``// if 'p' is a non- prime number then ` `            ``// prime[p] gives its largesr prime ` `            ``// factor ` `            ``if` `(prime[p] != ``0``) ` `                ``sum += prime[p]; ` `                 `  `            ``// 'p' is a prime number          ` `            ``else` `                ``sum += p; ` `        ``} ` `         `  `        ``// required sum ` `        ``return` `sum;      ` `    ``} ` `     `  `    ``// Driver program  ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `n = ``12``; ` `        ``System.out.println(``"Sum = "`  `                           ``+ sumOfLargePrimeFactor(n)); ` `    ``} ` `} ` ` `  ` `  `// This code is contributed  ` `// by Nikita Tiwari. `

## Python3

 `# Python3 code implementation to find ` `# sum of largest prime factor of  ` `# each number less than equal to n ` ` `  `# function to find sum of largest  ` `# prime factor of each number less ` `# than equal to n ` `def` `sumOfLargePrimeFactor( n ): ` ` `  `    ``# Create an integer array "prime[0..n]" ` `    ``# and initialize all entries of it  ` `    ``# as 0. A value in prime[i] will  ` `    ``# finally be 0 if 'i' is a prime,  ` `    ``# else it will contain the largest ` `    ``# prime factor of 'i'. ` `    ``prime ``=` `[``0``] ``*` `(n ``+` `1``) ` `    ``sum` `=` `0` `    ``max` `=` `int``(n ``/` `2``) ` `    ``for` `p ``in` `range``(``2``, ``max` `+` `1``): ` `         `  `        ``# If prime[p] is '0', then  ` `        ``# it is a prime number ` `        ``if` `prime[p] ``=``=` `0``: ` `             `  `            ``# Update all multiples of p ` `            ``for` `i ``in` `range``(p ``*` `2``, n ``+` `1``, p): ` `                ``prime[i] ``=` `p ` `                 `  `    ``# Sum up the largest prime factor ` `    ``# of all the numbers ` `    ``for` `p ``in` `range``(``2``, n ``+` `1``): ` `         `  `        ``# if 'p' is a non- prime  ` `        ``# number then prime[p] gives  ` `        ``# its largesr prime factor ` `        ``if` `prime[p]: ` `            ``sum` `+``=` `prime[p] ` `         `  `        ``# 'p' is a prime number ` `        ``else``: ` `            ``sum` `+``=` `p ` `     `  `    ``# required sum ` `    ``return` `sum` `     `  `# Driver code to test above function ` `n ``=` `12` `print``(``"Sum ="``, sumOfLargePrimeFactor(n)) ` ` `  `# This code is contributed by "Sharad_Bhardwaj". `

/div>

## C#

 `// C# implementation to find sum ` `// of largest prime factor of each ` `// number less than equal to n ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// function to find sum of largest ` `    ``// prime factorof each number ` `    ``// less than equal to n ` `    ``static` `int` `sumOfLargePrimeFactor(``int` `n) ` `    ``{ ` `        ``// Create an integer array "prime[0..n]" ` `        ``// and initialize all entries of it as 0. ` `        ``// A value in prime[i] will finally be 0 ` `        ``// if 'i' is a prime, else it will contain ` `        ``// the largest prime factor of 'i'. ` `        ``int``[] prime = ``new` `int``[n + 1]; ` `        ``int` `sum = 0; ` ` `  `        ``for` `(``int` `i = 1; i < n + 1; i++) ` `            ``prime[i] = 0; ` ` `  `        ``int` `max = n / 2; ` ` `  `        ``for` `(``int` `p = 2; p <= max; p++)  ` `        ``{ ` `            ``// If prime[p] is '0', then it is a ` `            ``// prime number ` `            ``if` `(prime[p] == 0) ` `            ``{ ` `                ``// Update all multiples of p ` `                ``for` `(``int` `i = p * 2; i <= n; i += p) ` `                    ``prime[i] = p; ` `            ``} ` `        ``} ` ` `  `        ``// Sum up the largest prime factor of all ` `        ``// the numbers ` `        ``for` `(``int` `p = 2; p <= n; p++) ` `        ``{ ` `            ``// if 'p' is a non- prime number then ` `            ``// prime[p] gives its largesr prime ` `            ``// factor ` `            ``if` `(prime[p] != 0) ` `                ``sum += prime[p]; ` ` `  `            ``// 'p' is a prime number ` `            ``else` `                ``sum += p; ` `        ``} ` ` `  `        ``// required sum ` `        ``return` `sum; ` `    ``} ` ` `  `    ``// Driver program ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 12; ` `        ``Console.WriteLine(``"Sum = "` `+ sumOfLargePrimeFactor(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

## PHP

 ` `

Output:

```Sum = 46
```