# Sum of Semi-Prime Numbers less than or equal to N

Given an integer **N**, the task is to find the sum of semi-prime numbers which are less than or equal to **N**. A Semi prime number is a number that is a multiple of two prime numbers.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:N = 6Output:10

4 and 6 are the semi primes â‰¤ 6

4 + 6 = 10Input:N = 10000000Output:9322298311255

**Approach:**

- First Calculate the primes less than or equal to N using Sieve and store them in a vector in sorted order.
- Iterate over the vector of primes. Fix one of the primes and starting checking the value of the product of all primes with this fixed prime.
- As the primes are arranged in sorted order, once we find a prime for which the product exceeds N, then it would exceed for all remaining primes. Hence, break the nested loop here.
- Add the product value to the answer variable for all valid pairs.

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `#define ll long long int` `// Vector to store the primes` `vector<ll> pr;` `// Create a boolean array "prime[0..n]"` `bool` `prime[10000000 + 1];` `void` `sieve(ll n)` `{` ` ` `// Initialize all prime values to be true` ` ` `for` `(` `int` `i = 2; i <= n; i += 1) {` ` ` `prime[i] = 1;` ` ` `}` ` ` `for` `(ll p = 2; (ll)p * (ll)p <= n; p++) {` ` ` `// If prime[p] is not changed then it is a prime` ` ` `if` `(prime[p] == ` `true` `) {` ` ` `// Update all multiples of p greater than or` ` ` `// equal to the square of it` ` ` `// numbers which are multiple of p and are` ` ` `// less than p^2 are already been marked` ` ` `for` `(ll i = (ll)p * (ll)p; i <= n; i += p)` ` ` `prime[i] = ` `false` `;` ` ` `}` ` ` `}` ` ` `// Print all prime numbers` ` ` `for` `(ll p = 2; p <= n; p++)` ` ` `if` `(prime[p])` ` ` `pr.push_back(p);` `}` `// Function to return the semi-prime sum` `ll SemiPrimeSum(ll N)` `{` ` ` `// Variable to store the sum of semi-primes` ` ` `ll ans = 0;` ` ` `// Iterate over the prime values` ` ` `for` `(` `int` `i = 0; i < pr.size(); i += 1) {` ` ` `for` `(` `int` `j = i; j < pr.size(); j += 1) {` ` ` `// Break the loop once the product exceeds N` ` ` `if` `((ll)pr[i] * (ll)pr[j] > N)` ` ` `break` `;` ` ` `// Add valid products which are less than` ` ` `// or equal to N` ` ` `// each product is a semi-prime number` ` ` `ans += (ll)pr[i] * (ll)pr[j];` ` ` `}` ` ` `}` ` ` `return` `ans;` `}` `// Driver code` `int` `main()` `{` ` ` `ll N = 6;` ` ` `sieve(N);` ` ` `cout << SemiPrimeSum(N);` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the above approach` `import` `java.util.*;` `class` `GFG` `{` `// Vector to store the primes` `static` `Vector<Long> pr = ` `new` `Vector<>();` `// Create a boolean array "prime[0..n]"` `static` `boolean` `prime[] = ` `new` `boolean` `[` `10000000` `+ ` `1` `];` `static` `void` `sieve(` `long` `n)` `{` ` ` `// Initialize along prime values to be true` ` ` `for` `(` `int` `i = ` `2` `; i <= n; i += ` `1` `)` ` ` `{` ` ` `prime[i] = ` `true` `;` ` ` `}` ` ` `for` `(` `int` `p = ` `2` `; (` `int` `)p * (` `int` `)p <= n; p++)` ` ` `{` ` ` `// If prime[p] is not changed then it is a prime` ` ` `if` `(prime[p] == ` `true` `)` ` ` `{` ` ` `// Update along multiples of p greater than or` ` ` `// equal to the square of it` ` ` `// numbers which are multiple of p and are` ` ` `// less than p^2 are already been marked` ` ` `for` `(` `int` `i = (` `int` `)p * (` `int` `)p; i <= n; i += p)` ` ` `prime[i] = ` `false` `;` ` ` `}` ` ` `}` ` ` `// Print all prime numbers` ` ` `for` `(` `int` `p = ` `2` `; p <= n; p++)` ` ` `if` `(prime[p])` ` ` `pr.add((` `long` `)p);` `}` `// Function to return the semi-prime sum` `static` `long` `SemiPrimeSum(` `long` `N)` `{` ` ` `// Variable to store the sum of semi-primes` ` ` `long` `ans = ` `0` `;` ` ` `// Iterate over the prime values` ` ` `for` `(` `int` `i = ` `0` `; i < pr.size(); i += ` `1` `)` ` ` `{` ` ` `for` `(` `int` `j = i; j < pr.size(); j += ` `1` `)` ` ` `{` ` ` `// Break the loop once the product exceeds N` ` ` `if` `((` `long` `)pr.get(i) * (` `long` `)pr.get(j) > N)` ` ` `break` `;` ` ` `// Add valid products which are less than` ` ` `// or equal to N` ` ` `// each product is a semi-prime number` ` ` `ans += (` `long` `)pr.get(i) * (` `long` `)pr.get(j);` ` ` `}` ` ` `}` ` ` `return` `ans;` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `long` `N = ` `6` `;` ` ` `sieve(N);` ` ` `System.out.println(SemiPrimeSum(N));` `}` `}` `// This code is contributed by Princi Singh` |

## Python3

`# Python3 implementation of the approach` `# Vector to store the primes` `pr` `=` `[]` `# Create a boolean array "prime[0..n]"` `prime ` `=` `[` `1` `for` `i ` `in` `range` `(` `10000000` `+` `1` `)]` `def` `sieve(n):` ` ` `for` `p ` `in` `range` `(` `2` `, n):` ` ` `if` `p ` `*` `p > n:` ` ` `break` ` ` `# If prime[p] is not changed then it is a prime` ` ` `if` `(prime[p] ` `=` `=` `True` `):` ` ` `# Update amultiples of p greater than or` ` ` `# equal to the square of it` ` ` `# numbers which are multiple of p and are` ` ` `# less than p^2 are already been marked` ` ` `for` `i ` `in` `range` `(` `2` `*` `p, n ` `+` `1` `, p):` ` ` `prime[i] ` `=` `False` ` ` ` ` `# Praprime numbers` ` ` `for` `p ` `in` `range` `(` `2` `, n ` `+` `1` `):` ` ` `if` `(prime[p]):` ` ` `pr.append(p)` `# Function to return the semi-prime sum` `def` `SemiPrimeSum(N):` ` ` `# Variable to store the sum of semi-primes` ` ` `ans ` `=` `0` ` ` `# Iterate over the prime values` ` ` `for` `i ` `in` `range` `(` `len` `(pr)):` ` ` `for` `j ` `in` `range` `(i,` `len` `(pr)):` ` ` `# Break the loop once the product exceeds N` ` ` `if` `(pr[i] ` `*` `pr[j] > N):` ` ` `break` ` ` `# Add valid products which are less than` ` ` `# or equal to N` ` ` `# each product is a semi-prime number` ` ` `ans ` `+` `=` `pr[i] ` `*` `pr[j]` ` ` ` ` `return` `ans` `# Driver code` `N ` `=` `6` `sieve(N)` `print` `(SemiPrimeSum(N))` `# This code is contributed by mohit kumar 29` |

## C#

`// C# implementation of the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG` `{` `// Vector to store the primes` `static` `List<` `long` `> pr = ` `new` `List<` `long` `>();` `// Create a boolean array "prime[0..n]"` `static` `bool` `[]prime = ` `new` `bool` `[10000000 + 1];` `static` `void` `sieve(` `long` `n)` `{` ` ` `// Initialize along prime values to be true` ` ` `for` `(` `int` `i = 2; i <= n; i += 1)` ` ` `{` ` ` `prime[i] = ` `true` `;` ` ` `}` ` ` `for` `(` `int` `p = 2; (` `int` `)p * (` `int` `)p <= n; p++)` ` ` `{` ` ` `// If prime[p] is not changed then it is a prime` ` ` `if` `(prime[p] == ` `true` `)` ` ` `{` ` ` `// Update along multiples of p greater than or` ` ` `// equal to the square of it` ` ` `// numbers which are multiple of p and are` ` ` `// less than p^2 are already been marked` ` ` `for` `(` `int` `i = (` `int` `)p * (` `int` `)p; i <= n; i += p)` ` ` `prime[i] = ` `false` `;` ` ` `}` ` ` `}` ` ` `// Print all prime numbers` ` ` `for` `(` `int` `p = 2; p <= n; p++)` ` ` `if` `(prime[p])` ` ` `pr.Add((` `long` `)p);` `}` `// Function to return the semi-prime sum` `static` `long` `SemiPrimeSum(` `long` `N)` `{` ` ` `// Variable to store the sum of semi-primes` ` ` `long` `ans = 0;` ` ` `// Iterate over the prime values` ` ` `for` `(` `int` `i = 0; i < pr.Count; i += 1)` ` ` `{` ` ` `for` `(` `int` `j = i; j < pr.Count; j += 1)` ` ` `{` ` ` `// Break the loop once the product exceeds N` ` ` `if` `((` `long` `)pr[i] * (` `long` `)pr[j] > N)` ` ` `break` `;` ` ` `// Add valid products which are less than` ` ` `// or equal to N` ` ` `// each product is a semi-prime number` ` ` `ans += (` `long` `)pr[i] * (` `long` `)pr[j];` ` ` `}` ` ` `}` ` ` `return` `ans;` `}` `// Driver code` `public` `static` `void` `Main(String[] args)` `{` ` ` `long` `N = 6;` ` ` `sieve(N);` ` ` `Console.WriteLine(SemiPrimeSum(N));` `}` `}` `// This code is contributed by Rajput-Ji` |

## Javascript

`<script>` `// Javascript implementation of the approach` `// Vector to store the primes` `let pr = [];` `// Create a boolean array "prime[0..n]"` `let prime = ` `new` `Array(10000000 + 1);` `function` `sieve(n)` `{` ` ` `// Initialize all prime values to be true` ` ` `for` `(let i = 2; i <= n; i += 1) {` ` ` `prime[i] = 1;` ` ` `}` ` ` `for` `(let p = 2; p * p <= n; p++) {` ` ` `// If prime[p] is not changed then it is a prime` ` ` `if` `(prime[p] == ` `true` `) {` ` ` `// Update all multiples of p greater than or` ` ` `// equal to the square of it` ` ` `// numbers which are multiple of p and are` ` ` `// less than p^2 are already been marked` ` ` `for` `(let i = p * p; i <= n; i += p)` ` ` `prime[i] = ` `false` `;` ` ` `}` ` ` `}` ` ` `// Print all prime numbers` ` ` `for` `(let p = 2; p <= n; p++)` ` ` `if` `(prime[p])` ` ` `pr.push(p);` `}` `// Function to return the semi-prime sum` `function` `SemiPrimeSum(N)` `{` ` ` `// Variable to store the sum of semi-primes` ` ` `let ans = 0;` ` ` `// Iterate over the prime values` ` ` `for` `(let i = 0; i < pr.length; i += 1) {` ` ` `for` `(let j = i; j < pr.length; j += 1) {` ` ` `// Break the loop once the product exceeds N` ` ` `if` `(pr[i] * pr[j] > N)` ` ` `break` `;` ` ` `// Add valid products which are less than` ` ` `// or equal to N` ` ` `// each product is a semi-prime number` ` ` `ans += pr[i] * pr[j];` ` ` `}` ` ` `}` ` ` `return` `ans;` `}` `// Driver code` ` ` `let N = 6;` ` ` `sieve(N);` ` ` `document.write(SemiPrimeSum(N));` `</script>` |

**Output:**

10