Sum of prime numbers without odd prime digits

0 0 6 minutes read

Given an integer N. The task is to find the sum of the first N prime numbers which don’t contain any odd primes as their digit.
Some of such prime numbers are 2, 11, 19, 29, 41 ……
Examples:

Input : N = 2
Output : 13
2 + 11 = 13
Input : N = 7
Output : 252

Approach :

We first use a Sieve of Eratosthenes to store all prime numbers.
Next check for each prime number if any odd prime digit is present or not.
If no such digit is present then we will include this prime to our required answer
Continue above step until we get N such prime numbers

Below is the implementation of the above approach :

C++

#include <bits/stdc++.h>
using namespace std;
 
#define MAX 100005
 
// Find all prime numbers
vector<int> addPrimes()
{
    int n = MAX;
 
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= n; p++) {
 
        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    vector<int> ans;
    // Store all prime numbers
    for (int p = 2; p <= n; p++)
        if (prime[p])
            ans.push_back(p);
 
    return ans;
}
 
// Function to check if a digit is odd prime or not
bool is_prime(int n) 
{
    return (n == 3 || n == 5 || n == 7);
}
 
// Function to find sum
int find_Sum(int n) 
{
    // To store required answer
    int sum = 0;
     
    // Get all prime numbers
    vector<int> v = addPrimes();
     
    // Traverse through all the prime numbers
    for (int i = 0; i < v.size() and n; i++) 
    {
        // Flag stores 1 if a number does 
        // not contain any odd primes
        int flag = 1;
        int a = v[i];
         
        // Find all digits of a number
        while (a != 0)
        {
            int d = a % 10;
            a = a / 10;
            if (is_prime(d)) {
                flag = 0;
                break;
            }
        }
         
        // If number does not contain any odd primes
        if (flag==1) 
        {
            n--;
            sum = sum + v[i];
        }
    }
 
    // Return the required answer
    return sum;
}
 
// Driver code
int main()
{
    int n = 7;
     
    // Function call
    cout << find_Sum(n); 
 
    return 0;
}

Java

// Java program for above approach
import java.util.*;
 
class GFG 
{
static int MAX = 100005;
 
// Find all prime numbers
static Vector<Integer> addPrimes()
{
    int n = MAX;
 
    boolean []prime = new boolean[n + 1];
    Arrays.fill(prime, true);
 
    for (int p = 2; p * p <= n; p++) 
    {
        if (prime[p] == true) 
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    Vector<Integer> ans = new Vector<Integer>();
     
    // Store all prime numbers
    for (int p = 2; p <= n; p++)
        if (prime[p])
            ans.add(p);
 
    return ans;
}
 
// Function to check if a digit
// is odd prime or not
static boolean is_prime(int n) 
{
    return (n == 3 || n == 5 || n == 7);
}
 
// Function to find sum
static int find_Sum(int n) 
{
    // To store required answer
    int sum = 0;
     
    // Get all prime numbers
    Vector<Integer> v = addPrimes();
     
    // Traverse through all the prime numbers
    for (int i = 0; i < v.size() && n > 0; i++) 
    {
        // Flag stores 1 if a number does 
        // not contain any odd primes
        int flag = 1;
        int a = v.get(i);
         
        // Find all digits of a number
        while (a != 0)
        {
            int d = a % 10;
            a = a / 10;
            if (is_prime(d))
            {
                flag = 0;
                break;
            }
        }
         
        // If number does not contain
        // any odd primes
        if (flag == 1) 
        {
            n--;
            sum = sum + v.get(i);
        }
    }
 
    // Return the required answer
    return sum;
}
 
// Driver code
public static void main(String[] args) 
{
    int n = 7;
     
    // Function call
    System.out.println(find_Sum(n)); 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for above approach
MAX = 100005
 
def addPrimes():
    n = MAX
 
    prime = [True for i in range(n + 1)]
 
    for p in range(2, n + 1):
 
        if p * p > n:
            break
 
        if (prime[p] == True):
            for i in range(2 * p, n + 1, p):
                prime[i] = False
 
    ans = []
     
    # Store all prime numbers
    for p in range(2, n + 1):
        if (prime[p]):
            ans.append(p)
 
    return ans
 
# Function to check if 
# a digit is odd prime or not
def is_prime(n):
    if n in [3, 5, 7]:
        return True
    return False
 
# Function to find sum
def find_Sum(n):
     
    # To store required answer
    Sum = 0
 
    # Get all prime numbers
    v = addPrimes()
 
    # Traverse through all the prime numbers
    for i in range(len(v)):
         
        # Flag stores 1 if a number does
        # not contain any odd primes
        flag = 1
        a = v[i]
 
        # Find all digits of a number
        while (a != 0):
 
            d = a % 10;
            a = a // 10;
            if (is_prime(d)):
                flag = 0
                break
 
        # If number does not contain any odd primes
        if (flag == 1):
            n -= 1
            Sum = Sum + v[i]
        if n == 0:
            break
 
    # Return the required answer
    return Sum
 
# Driver code
n = 7
 
# Function call
print(find_Sum(n))
 
# This code is contributed by Mohit Kumar

C#

// C# program for above approach
using System;
using System.Collections.Generic;
 
class GFG 
{
static int MAX = 100005;
 
// Find all prime numbers
static List<int> addPrimes()
{
    int n = MAX;
 
    Boolean []prime = new Boolean[n + 1];
    for(int i = 0; i < n + 1; i++)
        prime[i]=true;
 
    for (int p = 2; p * p <= n; p++) 
    {
        if (prime[p] == true) 
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    List<int> ans = new List<int>();
     
    // Store all prime numbers
    for (int p = 2; p <= n; p++)
        if (prime[p])
            ans.Add(p);
 
    return ans;
}
 
// Function to check if a digit
// is odd prime or not
static Boolean is_prime(int n) 
{
    return (n == 3 ||
            n == 5 || n == 7);
}
 
// Function to find sum
static int find_Sum(int n) 
{
    // To store required answer
    int sum = 0;
     
    // Get all prime numbers
    List<int> v = addPrimes();
     
    // Traverse through all the prime numbers
    for (int i = 0; 
             i < v.Count && n > 0; i++) 
    {
        // Flag stores 1 if a number does 
        // not contain any odd primes
        int flag = 1;
        int a = v[i];
         
        // Find all digits of a number
        while (a != 0)
        {
            int d = a % 10;
            a = a / 10;
            if (is_prime(d))
            {
                flag = 0;
                break;
            }
        }
         
        // If number does not contain
        // any odd primes
        if (flag == 1) 
        {
            n--;
            sum = sum + v[i];
        }
    }
 
    // Return the required answer
    return sum;
}
 
// Driver code
public static void Main(String[] args) 
{
    int n = 7;
     
    // Function call
    Console.WriteLine(find_Sum(n)); 
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
const MAX = 100005;
 
// Find all prime numbers
function addPrimes()
{
    let n = MAX;
 
    let prime = new Array(n + 1).fill(true);
 
    for (let p = 2; p * p <= n; p++) {
 
        if (prime[p] == true) {
            for (let i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    let ans = [];
    // Store all prime numbers
    for (let p = 2; p <= n; p++)
        if (prime[p])
            ans.push(p);
 
    return ans;
}
 
// Function to check if a digit is odd prime or not
function is_prime(n) 
{
    return (n == 3 || n == 5 || n == 7);
}
 
// Function to find sum
function find_Sum(n) 
{
    // To store required answer
    let sum = 0;
     
    // Get all prime numbers
    let v = addPrimes();
     
    // Traverse through all the prime numbers
    for (let i = 0; i < v.length && n > 0; i++) 
    {
        // Flag stores 1 if a number does 
        // not contain any odd primes
        let flag = 1;
        let a = v[i];
         
        // Find all digits of a number
        while (a != 0)
        {
            let d = a % 10;
            a = parseInt(a / 10);
            if (is_prime(d)) {
                flag = 0;
                break;
            }
        }
         
        // If number does not contain any odd primes
        if (flag==1) 
        {
            n--;
            sum = sum + v[i];
        }
    }
 
    // Return the required answer
    return sum;
}
 
// Driver code
    let n = 7;
     
    // Function call
    document.write(find_Sum(n)); 
 
</script>

Output :

Time Complexity : O(MAX + nlogm) where n is the number of primes less than or equal to MAX which is the defined constant and m is the maximum prime number less than or equal to MAX.

Auxiliary Space: O(MAX) where MAX is defined constant.

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 zambiatek!