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 numbersvector<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 notbool is_prime(int n) { return (n == 3 || n == 5 || n == 7);}// Function to find sumint 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 codeint main(){ int n = 7; // Function call cout << find_Sum(n); return 0;} |
Java
// Java program for above approachimport java.util.*;class GFG {static int MAX = 100005;// Find all prime numbersstatic 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 notstatic boolean is_prime(int n) { return (n == 3 || n == 5 || n == 7);}// Function to find sumstatic 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 codepublic 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 approachMAX = 100005def 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 notdef is_prime(n): if n in [3, 5, 7]: return True return False# Function to find sumdef 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 coden = 7# Function callprint(find_Sum(n))# This code is contributed by Mohit Kumar |
C#
// C# program for above approachusing System;using System.Collections.Generic;class GFG {static int MAX = 100005;// Find all prime numbersstatic 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 notstatic Boolean is_prime(int n) { return (n == 3 || n == 5 || n == 7);}// Function to find sumstatic 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 codepublic 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 numbersfunction 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 notfunction is_prime(n) { return (n == 3 || n == 5 || n == 7);}// Function to find sumfunction 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 :
252
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
