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:
Input: N = 6
Output: 10
4 and 6 are the semi primes ? 6
4 + 6 = 10
Input: N = 10000000
Output: 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 primesvector<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 sumll 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 codeint main(){ ll N = 6; sieve(N); cout << SemiPrimeSum(N); return 0;} |
Java
// Java implementation of the above approachimport java.util.*;class GFG{// Vector to store the primesstatic 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 sumstatic 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 codepublic 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 primespr=[]# 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 # Print all prime numbers for p in range(2, n + 1): if (prime[p]): pr.append(p)# Function to return the semi-prime sumdef 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 codeN = 6sieve(N)print(SemiPrimeSum(N))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;class GFG{// Vector to store the primesstatic 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 sumstatic 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 codepublic 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 primeslet 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 sumfunction 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
Auxiliary Space: O(10000000)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
