Sum of first N primes with no odd prime digit

Last Updated on March 31, 2022 by Ria Pathak

Concepts Used:

Mathematics

Difficulty Level:

Medium

Problem Statement (Simplified):

For a given number N, find the sum of first N primes which don’t contain any odd prime digits (3,5,7) in them.
See original problem statement here

Test Case:

Input:
2
3
4

Output:
32 
61

Explanation:
Case-1:
First 10 prime numbers are 2,3,5,7,11,13,17,19,23,29. Out of which first 3 prime numbers with no odd prime digits are 2,11,19 and their sum is 2+11+19 => 32. So, 32 is our answer.

Case-2:
First 10 prime numbers are 2,3,5,7,11,13,17,19,23,29. Out of which first 4 prime numbers with no odd prime digits are 2,11,19,29 and their sum is 2+11+19+29 => 61. So, 61 is our answer.

Solving Approach :

1) For the primality check, we can use ‘Sieve of Eratosthenes’ for creating an array containing prime numbers.

Sieve of Eratosthenes : We create an array of size 100006 here, where each index return if the index is prime or not. We initialize an array with all True values. We iterate from 1 to 100006 and set False to all multiples of the current number. After all the iterations, we’ll receive an array containing True values at indices which are prime. So now, if we have to check if n is prime or not we return the value of array[n] if it’s True, n is prime else not.

2) After we have got primality check covered, we now check if a given number is prime or not, if it’s prime, we check if it contains an odd prime digit (3,5,7) or not, if no, we add the number to sum and decrease the N by 1.
3) After N is 0, we print the final sum.

Example:

• Sieve of Eratosthenes : Let’s assume we want to create a ‘Sieve of Eratosthenes’ for numbers from ‘1’ to ’20’. We create an array, where all elements contain 1 as default value which means we assume them prime by default.

• We then iterate from ‘2’ to ’20’ and mark all of their multiples by 0, which means they are not prime. Indexes containing ‘1’ after this are numbers that are prime and there exists no number from 2 to 20 which divides them completely except themselves.

• Now, we have to create an array of ‘100006’ elements for primality check using the above method, so that we have all prime numbers from ‘1’ to ‘100006’.

• We’ve created our array for primality check, now we can calculate the sum for our test cases.

• Let’s take ‘n = 4’, we check all numbers from 2 to 100006 until we found ‘n’ numbers with no odd prime digit.

• For every number we check if it is ‘prime’ or not, if ‘yes’, we check if any of it’s digit contains any of odd prime digit(i.e. 3 or 5 or 7), if ‘no’, the current number is our required number, so we add this to our sum.

• For the above test case, such numbers are ‘2,11,19,29’, as all of these numbers are ‘prime’ and do not contain ‘3’ or ‘5’ or ‘7’ as their digits.

Solutions:

#include
int primes[100006];

void setPrimes(){

  for(int i=2; i<100006; i++)
    primes[i] = 1;

  primes[0] = 0;
  primes[1] = 0;

  for(int i=2; i<100006;i++){
    for(int j=2*i; j<100006; j+=i){
      primes[j] = 0;
    }
  }

}

int main()
{
  setPrimes();
  int test;
  scanf("%d", &test);
    while(test--){
      int n ;
      scanf("%d", &n);
      int sum = 0, i=2;

      while(n!=0){

        if( primes[i]==1 ){
            int k = i;
            int odd = 0;
            while(k){
                if(primes[k%10] == 1 && k%10 != 2){
                    odd = 1;
                    break;
                }
                k/=10;
            }
            if(odd==0){
                sum += i;
                n--;
            }
        }
        i++;
      }
      printf("%d\n",sum);
    }
}

#include 
using namespace std;

int primes[100006];

void setPrimes(){

  for(int i=2; i<100006; i++)
    primes[i] = 1;

  primes[0] = 0;
  primes[1] = 0;

  for(int i=2; i<100006;i++){
    for(int j=2*i; j<100006; j+=i){
      primes[j] = 0;
    }
  }

}

int main()
{
  setPrimes();
  int test;
  cin>>test;

    while(test--){
      int n ;
      cin>>n;
      int sum = 0, i=2;

      while(n!=0){

        if( primes[i]==1 ){
            int k = i;
            int odd = 0;
            while(k){
                if(primes[k%10] == 1 && k%10 != 2){
                    odd = 1;
                    break;
                }
                k/=10;
            }
            if(odd==0){
                sum += i;
                n--;
            }
        }
        i++;
      }

      cout<
						 

import java.util.*;
import java.io.*;

public class Main {
  static int primes[] = new int[100006];

  static void setPrimes(){

    for(int i=2; i<100006; i++)
      primes[i] = 1;

    primes[0] = 0;
    primes[1] = 0;

    for(int i=2; i<100006;i++){
      for(int j=2*i; j<100006; j+=i){
        primes[j] = 0;
      }
    }

  }


  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    setPrimes();
    int test = sc.nextInt();
     while(test != 0){
        int n = sc.nextInt() ;
        int sum = 0, i=2;

        while(n!=0){

          if( primes[i]==1 ){
              int k = i;
              int odd = 0;
              while(k!=0){
                  if(primes[k%10] == 1 && k%10 != 2){
                      odd = 1;
                      break;
                  }
                  k/=10;
              }
              if(odd==0){
                  sum += i;
                  n--;
              }
          }
          i++;
        }
        System.out.println(sum);
        test--;
      }
  }
}

primes = [0] * 100006

def setPrimes():

	global primes

	for i in range(2, 100006):
		primes[i] = 1

	primes[0] = 0
	primes[1] = 0

	for i in range(2, 100006):

		for j in range(2 * i, 100006, i):
			primes[j] = 0

setPrimes()
for _ in range(int(input())):

	n = int(input())
	sum = 0
	i = 2

	while(n!=0):
		if( primes[i] == 1 ):
			k = i
			odd = 0
			while(k):
				if(primes[k % 10] == 1 and k % 10 != 2):
					odd = 1
					break
				
				k//=10
			
			if(odd == 0):
				sum += i
				n -= 1

		i += 1

	print(sum)

[forminator_quiz id="837"]

This article tried to discuss the concept of Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Mathematics you can check out MYCODE | Competitive Programming.