{"id":835,"date":"2020-06-11T10:14:52","date_gmt":"2020-06-11T10:14:52","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=835"},"modified":"2022-03-31T11:57:44","modified_gmt":"2022-03-31T11:57:44","slug":"sum-of-first-n-primes-with-no-odd-prime-digit","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/sum-of-first-n-primes-with-no-odd-prime-digit\/","title":{"rendered":"Sum of first N primes with no odd prime digit"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used:<\/h3>\n
\n

Mathematics<\/p>\n<\/blockquote>\n

Difficulty Level:<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

For a given number N<\/code>, find the sum of first N<\/code> primes which don’t contain any odd prime digits (3,5,7) in them.
\n<\/strong><\/u><\/a><\/p>\n

Test Case:<\/h4>\n<\/blockquote>\n
Input:\n2\n3\n4\n\nOutput:\n32 \n61\n\nExplanation:\nCase-1:\nFirst 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.\n\nCase-2:\nFirst 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.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
\n
1) For the primality check, we can use ‘Sieve of Eratosthenes’ for creating an array containing prime numbers.<\/p>\n
Sieve of Eratosthenes<\/code> : 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<\/code> values. We iterate from 1 to 100006 and set False<\/code> to all multiples of the current number. After all the iterations, we’ll receive an array containing True<\/code> values at indices which are prime. So now, if we have to check if n<\/code> is prime or not we return the value of array[n]<\/code> if it’s True<\/code>, n<\/code> is prime else not.<\/p>\n
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<\/code> by 1.
\n3) After N<\/code> is 0, we print the final sum.<\/p>\n<\/blockquote>\n
Example:<\/h4>\n
\n
    \n
  • \n
    Sieve of Eratosthenes<\/code> : 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.<\/p>\n<\/li>\n
  • \n
    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.<\/p>\n<\/li>\n
  • \n
    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’.<\/p>\n<\/li>\n
  • \n
    We’ve created our array for primality check, now we can calculate the sum for our test cases.<\/p>\n<\/li>\n
  • \n
    Let’s take ‘n = 4’, we check all numbers from 2 to 100006 until we found ‘n’ numbers with no odd prime digit.<\/p>\n<\/li>\n
  • \n
    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.<\/p>\n<\/li>\n
  • \n
    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.<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
    Solutions:<\/h4>\n\t\t\t\t\t\t